二叉搜索树的后序遍历序列

问题陈述

输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树:

1
2
3
4
5
    5
/ \
2 6
/ \
1 3

示例 1:

输入: [1,6,3,2,5]
输出: false

思路分析

二叉搜索树:左子树的值小于根,右子树的值大于根。

后序遍历:左右根。如上示例,后序遍历为13265。

递归判断:具体见代码注释。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
return recurr(postorder,0,postorder.size()-1); //递归判断,初始化i=0,j=postorder.size()-1

}
bool recurr(vector<int>& postorder,int i,int j){
if(i>=j) return true; //结点数小于等于1的情况
int p=i;
while(postorder[p]<postorder[j]) p++; //小于根结点的为左子树
int m=p; //记录此时的p,如上例为6
while(postorder[p]>postorder[j]) p++; //大于根结点的为右子树,p++后若为正确的后序序列则p==j
return p==j&&recurr(postorder,i,m-1)&&recurr(postorder,m,j-1); //继续判断下一级的左右子树,即132和6
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public boolean verifyPostorder(int[] postorder) {
return recur(postorder, 0, postorder.length - 1);
}
boolean recur(int[] postorder, int i, int j) {
if(i >= j) return true;//说明子树节点数<=1
int p = i;
while(postorder[p] < postorder[j]) p++;
int m = p;
while(postorder[p] > postorder[j]) p++;
return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);
}
}