首页 > 代码库 > Recover Binary Search Tree
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.
中序遍历整棵树，bst的节点值则是有序的，如果发现前驱节点值大于当前节点值，那么就是异常情况
异常情况有两种，一种是前后相连的节点，另一种是不相连的节点，代码如下：
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */10 class Solution {11 public:12 void recoverTree(TreeNode *root) {13 if( !root ) return ;14 stack<TreeNode*> st;15 TreeNode* cur = root;16 while( cur ) {17 st.push(cur);18 cur = cur->left;19 }20 TreeNode* pre = 0;21 TreeNode* fnode = 0;22 TreeNode* snode = 0;23 while( !st.empty() ) {24 cur = st.top();25 st.pop();26 if( pre && pre->val > cur->val ) { //前驱值大于当前节点值时则为异常情况27 if( !fnode ) fnode = pre, snode = cur; //可能出现出错的两个节点刚好是前后连续的28 else {29 snode = cur; //再次找到前驱值大于当前节点值，那么他们就不是相连的30 break;31 }32 }33 pre = cur;34 cur = cur->right;35 while( cur ) {36 st.push(cur);37 cur = cur->left;38 }39 }40 swap(fnode->val, snode->val); //交换两节点的值41 }42 };
Recover Binary Search Tree
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。