shubo的博客

gopher/全干工程师

0%

二叉搜索树后序遍历序列

发表于 更新于
本文字数： 835 阅读时长 ≈ 1 分钟

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

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

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

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

示例 1：

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

示例 2：

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

思路

由题意知：

二叉搜索树中，左节点<根节点<右节点。

后序遍历顺序：左、右、根。立即推=>根节点就是序列的最后一个元素。

递归：

设本次递归序列的左右边界为i,j。
递归结束条件：
    如果i>=j，立即推=>当前子树的节点数<=1,直接返回true。
递推过程：
    1.从左向右找第一个大于根节点的值，索引记作m。
    2.则可以将序列划分为两个区间 `[i,m-1]` `[m,j]`
    3.此时经过了一次升序和降序的扫描，如果扫描到最后则返回true；
    4.递归左右两个区间，都返回true才是正确的二叉搜索树后序序列。

代码(JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);
    }
    public boolean recur(int[] postorder,int i,int j){
        if(i>=j) return true;

        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);
    }
}