A1043 Is It a Binary Search Tre

2017-09-19  本文已影响22人  土豆有点

A1043中柳诺的写法要完全优于算法笔记给出的答案,其中对于怎么把先序遍历转换成后序遍历的方法很赞。

void getpost(int root, int tail){// 用了递归, root-头, tail--尾, 分而治之--很像快速排序的写法
    if(root > tail)//递归边界1
        return;
    
    int  i = root + 1;
    int j = tail;
    if(!isMirror){
        while(i <= tail && pre[root] > pre[i])
            i++;
        while(j > root && pre[root] <= pre[j])
            j--;
    }
    else{ //这里利用了二叉查找树的性质,而且像是利用了双指针
        while(i <= tail && pre[root] <= pre[i]) 
            i++;
        while(j > root && pre[root] > pre[j])
            j--;
    }
    
    if(i - j != 1)
        return;
    
    getpost(root + 1, j);//递归式 -- 左子树   !!这二个顺序不能换
    getpost(i, tail);//递归式 -- 右子树
    
    post.push_back(pre[root]); //后序  怎么将先序转换成后序
}
上一篇下一篇

猜你喜欢

热点阅读