剑指Offer_23

发表于 | 分类于

题目

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

解题思路

解法一：

非递归版本

对于二叉搜索树的节点来说，它总是大于左子树所有的节点，小于右子树所有的节点。这样就可以一一检查每个节点是否符合条件。

因为数组是后续遍历的结果，所以各个子树的根节点在数组末尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        int N = sequence.length-1;
        int i = 0;
        while(N != 0){
        	//N节点左子树小于根节点 以及 大于根节点 
            while(i < N && sequence[i++] < sequence[N]){}
            while(i < N && sequence[i++] > sequence[N]){}
            if(i != N){
                return false;
            }
            i = 0;
            --N;
        }
        return true;
    }
}

解法二：

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    private boolean helper(int []sequence, int N){
        if(N == 0){
            return true;
        }
        int i = 0;
        while(i < N && sequence[i++] < sequence[N]){}
        while(i < N && sequence[i++] > sequence[N]){}
        if(i != N){
            return false;
        }
        return helper(sequence, --N);
    }
    
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        return helper(sequence, sequence.length-1);
    }
    
}