Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: void recoverTree(TreeNode *root) { pre = n1 = n2 = NULL; dfs(root); n1->val ^= n2->val; n2->val ^= n1->val; n1->val ^= n2->val; } private: TreeNode *pre,*n1,*n2; void dfs(TreeNode *root) { if(root == NULL) return; dfs(root->left); if(pre != NULL &&pre->val > root->val) { n1 = root; if(n2 == NULL) n2 = pre; } pre = root; dfs(root->right); } };