题目: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.
思路:
本质上是中序遍历:
思路是这样的,进行中序遍历,严格按照从小到大的顺序,如果出现前一个值大于当前节点值,看一下是不是第一个出现大小不一致的情况,
这是把前面的节点保存为第一个,如果后面没有出现大小不一的情况,则仅仅交换刚刚两个节点。
如果出现两次,把第二次的根节点保存早第二个节点变量里面。
代码:
class Solution { public: void recoverTreeHelper(TreeNode *root){ if(root==NULL) return; recoverTreeHelper(root->left); if(prev){ if(prev->val>root->val){ if(n1==NULL){ n1=prev; } n2=root; } } prev=root; recoverTreeHelper(root->right); } void recoverTree(TreeNode *root) { recoverTreeHelper(root); if(n1&&n2){ swap(n1->val,n2->val); } } private: TreeNode *n1=NULL,*n2=NULL,*prev=NULL; };