剑指 Offer 33.二叉搜索树的后序遍历序列

题目描述

原题
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
参考以下这颗二叉搜索树:
1
5
2
/ \
3
2 6
4
/ \
5
1 3
Copied!
示例 1:
1
输入: [1,6,3,2,5]
2
输出: false
Copied!
示例 2:
1
输入: [1,3,2,6,5]
2
输出: true
Copied!
提示:
    1.
    数组长度 <= 1000

题解

递归

1
class Solution {
2
public boolean verifyPostorder(int[] postorder) {
3
return recur(postorder,0,postorder.length-1);
4
}
5
public boolean recur(int[] postorder,int i,int j){
6
if(i > = j ) return true;
7
int p = i;
8
while(postorder[p]<postorder[j]) p++;
9
int m = p; //右子树的第一个节点
10
//如果是后续遍历 则排列的顺序是 左子树 右子树 根节点
11
while(postorder[p]>postorder[j]) p++;
12
//经过两次循环p必然等于j如果不等则说明不是
13
//分别递归左子树和右子树
14
return p==j&&recur(postorder,i,m-1)&&recur(postorder,m,j-1);
15
}
16
}
Copied!
最近更新 9mo ago
复制链接