二叉搜索树中的错误节点

找到搜索二叉树中两个错误的节点

http://www.nowcoder.com/questionTerminal/9caad175642e4651a175e6993df9d8b2

二叉搜索树,如果正确采取中序遍历,将是一个递增的序列。
例如正确的中序情况:1 2 3 4 5
那么交换其中任意两个节点情况:

可以发现,其本质是寻找逆序对,可能只有一组1 3 2 4 5
可能有两组:1 5 3 4 2 或 1 4 3 2 5

那么只需要中序遍历二叉树,找到逆序对,第一个数,最后一个数

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
int main()
{
    int n,root;
    cin>>n>>root;
    vector<int> l(n+1,0);
    vector<int> r(n+1,0);
    for(int i=0;i<n;i++)
    {
        int fa,lc,rc;
        cin>>fa>>lc>>rc;
        l[fa]=lc;
        r[fa]=rc; 
    }
    int error1=0;
    int error2=0;//记录下错误节点
    stack<int> stk;
    int p=root;
    int pre=0;
    while(stk.empty()==false || p!=0) 
    {
        if(p!=0) //当前研究节点
        {
            stk.push(p);//入栈
            p=l[p];//移动到左边节点
        }
        else
        {
            int top=stk.top();
            stk.pop();
            if(top<pre)  //找到一组逆序对
            {
                if(error1==0)
                    error1=pre;
                error2=top;
            }
            pre=top;//填充pre
            p=r[top];//  转移到右子树
        }
    }
    if(error1<error2)
        cout<<error1<<" "<<error2<<endl;
    else
        cout<<error2<<" "<<error1<<endl;
}
全部评论

相关推荐

07-07 14:30
复旦大学 Java
遇到这种人我也不知道说啥了
正义执行官:人家能回你就不错了,自己不主动去问,等着天上掉馅饼,想啥呢哥们
点赞 评论 收藏
分享
07-01 13:37
门头沟学院 Java
steelhead:不是你的问题,这是社会的问题。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 10:39
一个证都没&nbsp;我能填什么
程序员小白条:别人有,你为什么没有,还是这个道理,社会就是比较,竞争,淘汰,你要安逸,那么就要做好淘汰的准备
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务