首页 > 其他 > 详细

99. Recover Binary Search Tree (Tree; DFS)

时间:2015-10-04 11:02:52      阅读:257      评论:0      收藏:0      [点我收藏+]

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?

 
法I:BST的中序遍历结果是递增序列。把这个递增序列存储到数组中,再遍历一遍数组,便可知道swap的两个元素
class Solution {
public:
    void recoverTree(TreeNode *root) {
        vals.clear();
        treeNodes.clear();
        inorderTraverse(root);
        
        sort(vals.begin(), vals.end());
        for (int i = 0; i < treeNodes.size(); ++i)
        {
            treeNodes[i]->val = vals[i]; //只改变值,不改结构
        }
    }
    
    void inorderTraverse(TreeNode* root)
    {
        if (!root)
            return;
        
        inorderTraverse(root->left);
        vals.push_back(root->val);
        treeNodes.push_back(root);
        inorderTraverse(root->right);        
    }
private:
    vector<int> vals;  
    vector<TreeNode*> treeNodes;  
};

 

法II:空间复杂度O(1)的解决方案。在中序遍历的时候,当第一次扫描到前一个节点>后一个节点,
  1. 如果是后一个节点错了,那么它只可能与前一个节点对换位置
  2. 如果是前一个节点错了,那么可能是与它后面的某个节点对换位置

所以令n1=前个节点,n2=后个节点。继续扫描,如果再次出现错误,那么n2必定=出现错误的后个节点

class Solution {
public:
    void recoverTree(TreeNode *root) {
        TreeNode *n1=NULL;
        TreeNode *n2=NULL;
        TreeNode *prev=NULL;
        findTwoNodes(root,n1,n2,prev);
        
        if(n1!=NULL && n2!=NULL)
        {
            int tmp=n2->val;
            n2->val=n1->val;
            n1->val=tmp;
        }
    }
    void findTwoNodes(TreeNode *root, TreeNode *&n1, TreeNode *&n2, TreeNode *&prev)
    {
        if(root==NULL) return;
        
        findTwoNodes(root->left,n1,n2,prev);
        if(prev!=NULL && prev->val > root->val)
        {
            n2=root;
            if(n1==NULL) //说明是第一次遍历到出错点
            {
                n1=prev;
            }
        }
        prev=root;
        findTwoNodes(root->right,n1,n2,prev);
    }
};

 

 

99. Recover Binary Search Tree (Tree; DFS)

原文:http://www.cnblogs.com/qionglouyuyu/p/4854218.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!