Recover
Binary Search Tree:
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?
/** * 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* w1,*w2; void recoverTree(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function w1=NULL; w2=NULL; TreeNode* pre=NULL; inorder(root,pre); assert(w1&&w2); swap(w1->val,w2->val); } void inorder(TreeNode* root,TreeNode*& pre) { if (!root ) return ; inorder(root->left,pre); if (pre&& pre->val>=root->val) { if (w1==NULL) { w1=pre; w2=root; } else { w2=root; } } pre=root; inorder(root->right,pre); } };