剑指offer第二十三题。

题目描述

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

解题思路

首先要了解二叉搜索树的重要性质：根节点root的所有左子树的值都小于他，右子树的所有值都大于他。并且一个节点的值大于他的左孩子的值，小于右孩子的值。

比如这个树就满足二叉搜索树的性质：

1
2
3
4
5
6
7
二叉搜索树示例：

         20
       /  \
      15   25
     / \  
    10 18

那么它的后续遍历是 10 18 15 25 20

显然，数组的最后一个值是树的root，25是其右子树，10-15都是其左子树，那么前三个数都要比20小，这样才能满足条件。然后再以15为root，递归判断。

我的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0){
            return false;
        }
        if(sequence.length == 1){
            return true;
        }
        return judge(sequence,0,sequence.length-1);
    }
    
    private boolean judge(int[] sequence,int start,int end){
        //递归的停止条件
        if(start >= end){
            return true;
        }
        //从后往前找到第一个比end小的数
        int i = end-1;
        while(i>start && sequence[i] > sequence[end]){
            i--;
        }
        //0-end都应该是左子树，所以值必须都比root小，有一个大则false
        for(int j=0;j<i;j++){
            if(sequence[j] > sequence[end]){
                return false;
            }
        }
        
        //对左右子树再做递归判断
        return judge(sequence,0,i) && judge(sequence,i,end-1);
    }
}