問題描述 wo elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note: A solution using O(n) space is PRetty straight forward. Could you devise a constant space solution? Subscribe to see which companies asked this question.
解決思路 使用inorder遍歷的辦法，因為在二叉查詢樹時，inorder遍歷會滿足遍歷到的節點是有序的，而此時為升序，所以我們只要找到兩個不滿足pre->val < cur->val的節點就可以了。
代碼
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: TreeNode* first=NULL; TreeNode* second=NULL; TreeNode* pre = new TreeNode(INT_MIN); void recoverTree(TreeNode* root) { helper(root); int tmp = first->val; first->val = second->val; second->val = tmp; } void helper(TreeNode* root) { if (root == NULL) return; helper(root->left); if (!first && pre->val >= root->val) first = pre; if (first && pre->val >= root->val) {second = root; } pre = root; helper(root->right); }};新聞熱點
疑難解答
