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

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

题目

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

思路

• 主要思想：递归
• 题目要点：
  • 二叉搜索树的特点：1）左子树的节点都比根节点小，右子树的节点都比根节点大；2）中序遍历过后是个有序序列
  • 二叉搜索树后序遍历序列的特点：1）根节点在序列的最后；2）可现根据根节点划分左右子树，而后根据利用递归处理左右子树，从而验证其是否是二叉搜索树的后序遍历序列。

代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0)
            return false;
        if (sequence.length == 1)
            return true;
        return helper(sequence, 0, sequence.length - 1);
    }
    
    public boolean helper(int[] sequence, int start, int root) {
        if (start >= root) {
            return true;
        }
        //划分左子树和右子树
        int i = root;
        while (i > start && sequence[i-1] > sequence[root])
            i--;
        //[0，i-1]是左子树，[i, root-1]是右子树
        for (int j = start; j < i; j++) {
            if (sequence[j] > sequence[root]) {
                return false;
            }
        }
        //对左右子树进行递归
        return helper(sequence, start, i-1) && helper(sequence, i, root - 1);
    }
}