Revocer BST

8月 6 2014

这道题目看起来思路很好想，BST中序就是排序，等价于找排序数组调换的两个元素，一开始分析拿几个例子，大概有两种要注意，一种是相邻swith，一种是涉及到头尾的switch，大致组合四种
case，但是后来发现其实就是相邻switch这一种情况，相邻只有一次decrease，否则有两次，头尾可以归纳到相邻，而且自己犯了一次错误，以为相邻只要记住第一个，然后后面next访问就可以了，
后来发现其实是BST，没next= =通过InOrder遍历找，于是也要记录miss2node, 第二次reverse刚好可以覆盖成新的，正好正确。

代码：

void recoverTree(TreeNode *root) {
        stack<TreeNode*> s;
        TreeNode*p=root, *mis1node, *mis2node, *lastp=NULL;

        int reversecount=0;
        while(!s.empty()||p!=NULL)
        {
            while(p!=NULL)
            {
                if(lastp!=NULL && lastp->val>p->val)
                {
                    reversecount++;
                    if(reversecount==1)
                    {
                        mis1node=lastp;
                        mis2node=p;
                    }
                    else if(reversecount==2)
                    {
                        mis2node=p;
                    }
                }

                lastp=p;
                s.push(p);
                p=p->left;
            }
            p=s.top();
            s.pop();
            p=p->right;
        }

        if(reversecount==2|| reversecount==1)
        {
            swap(mis1node->val,mis2node->val);
        }
    }

Posted by richard爱闹 - 8月 6 2014
如需转载，请注明：本文来自 Richard

留言