JZ23 二叉搜索树的后序遍历序列*
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
思路
首先,要知道什么是二叉搜索树:对于任何一棵子树来说,根节点都比它的左子树大,比它的右子树小
二叉搜索树有什么特点呢?
下面是一棵二叉搜索树:
10 / \ 8 13 / \ / \ 7 9 11 17
前序遍历:10,8,7,9,13,11,17;
第一个是根节点,后面分别为它的左右子树(左都比它小,右都比它大)
中序:7,8,9,10,11,13,17;
中序遍历单调递增
后序遍历:7,9,8,11,17,13,10
最后一个节点是根节点,前面分别为它的左子树和右子树(左都比它小,右都比它大)
用递归的思想
关键点:
(1)找这个序列中左右子树的分界点
(2)递归分别判断左右子树
我的错误:
未考虑特殊情况(没有左子树或者没有右子树的情况)
一开始我的bound没有给初始值,所以出错了,不能只想着最一般的情况!!!
代码
class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.size()<=0) return false; int left=0; int right=sequence.size()-1; return Verify(sequence,left,right); } bool Verify(vector<int> sequence,int left,int right) { if(left>=right) return true; int root=sequence[right]; int flag=0; //标志出现了比根节点大的数,0表示没有出现,1表示出现了 int bound=0; //定义小于和大于之间的边界 for(int i=left;i<right;i++) { if(sequence[i]>root && flag==0) { bound=i; flag=1; //出现之后flag变为1 } else if(sequence[i]<root && flag==1) { return false; //如果在flag=1(已经有比根节点大了数了还出现了比根节点小的,那就返回false) } } return Verify(sequence,left,bound-1)&& Verify(sequence,bound,right-1); } };