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]); //后序 怎么将先序转换成后序
}