Two 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?
confused what "{1,#,2,3}"
means? >
read more on how binary tree is serialized on OJ.
思路:BST树的中序遍历是非递减序列
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* mis_1; TreeNode* mis_2; TreeNode* pre; void recoverTreeHelper(TreeNode* root) { if(root == NULL) { return; } if(root->left != NULL) { recoverTreeHelper(root->left); } if (pre != NULL && pre->val > root->val) { if (mis_1 != NULL) { mis_2 = root; } else { mis_1 = pre; mis_2 = root; } } pre = root; if(root->right != NULL) { recoverTreeHelper(root->right); } } void swap(TreeNode* a, TreeNode* b) { int tmp = a->val; a->val = b->val; b->val = tmp; } void recoverTree(TreeNode *root) { if (root == NULL) { return; } mis_1 = NULL, mis_2 = NULL, pre = NULL; recoverTreeHelper(root); swap(mis_1,mis_2); } };