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.
The serialization of a binary tree follows a level order traversal, where ‘#‘ signifies a path terminator where no node exists below.
Here‘s an example:
1
/ 2 3
/
4
5
The above
binary tree is serialized
as "{1,2,3,#,#,4,#,#,5}".
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void recoverMistake(TreeNode *root,TreeNode *&first,TreeNode *&second,TreeNode *&pPre) { if(root==NULL) return; recoverMistake(root->left,first,second,pPre); if(pPre && pPre->val>root->val) { if(first==NULL) { first=pPre; second=root; } else { second=root; } } pPre=root; recoverMistake(root->right,first,second,pPre); } void recoverTree(TreeNode *root) { TreeNode *first=NULL,*second=NULL,*pPre=NULL; recoverMistake(root,first,second,pPre); swap(first->val,second->val); } };
Recover Binary Search Tree,布布扣,bubuko.com
原文：http://www.cnblogs.com/awy-blog/p/3724868.html