leetcode: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?
confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.
OJ's Binary Tree Serialization:
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}".
题意二叉查找树不合法,有两个节点的值被交换了,找出这两个节点并且不改变树的结构,使得二叉查找树合法,常数空间限制。
这题的要点就是想到使用树的递归中序遍历,因为二叉查找树合法的情况,中序遍历的值是从小到大排列的。
当出现当前值比前一个值小的时候,就是存在不合法的节点。
用pre存中序遍历时当前节点的前一个节点,方便值的大小对比,用s1,s2记录这两个不合法序列的位置,s1存较大的值,s2存较小的值。
最后把两个不合法的值交换。
/** * 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 *s1,*s2,*pre; void hehe(TreeNode *root) { if(!root)return ; hehe(root->left); if(pre&& pre->val > root->val) { if(s1==NULL)s1=pre,s2=root; else s2=root; } pre=root; hehe(root->right); } void recoverTree(TreeNode *root) { if(!root)return ; s1=s2=pre=NULL; hehe(root); swap(s1->val,s2->val); } }; // http://blog.csdn.net/havenoidea
补充:软件开发 , C++ ,