题解 | #二叉搜索树的后序遍历序列#

# -*- coding:utf-8 -*-
class Solution:
    def VerifySquenceOfBST(self, sequence):
        # write code here
        if not sequence:
            return False
        # 递归
        return self.check(sequence, 0, len(sequence) - 1)

    def check(self, sequence, left, right):
        if left >= right:
            return True
        # 找到第一个大于根节点的元素
        mid = left
        root = sequence[right]
        while sequence[mid] < root: mid += 1 tmp = mid # 保障postorder[mid]后的数要大于root,否则返回false while tmp < right: tmp += 1 if sequence[tmp] < root: return False # 递归左右子树进行判断 return self.check(sequence, left, mid - 1) and self.check(sequence, mid, right - 1)

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 判断是否师空序列
        if (sequence.length == 0){
            return false;
        }
        return dfs(sequence, 0, sequence.length);
    }
    
    private boolean dfs(int[] sequence, int start, int end) {
        if (start >= end - 1)
            return true;
        // 根结点是最后一个元素
        int root = sequence[end - 1];
        // 左子树都比根结点小，右子树都比根结点大
        int i = start;
        while (i < end && sequence[i] < root) // i 为左右子树的边界 ++i; // 判断右子树是否比根节点大 for (int j = i; j < end; ++j) if (sequence[j] < root) return false; // 对序列的前后两部分进行递归调用 return dfs(sequence, start, i) && dfs(sequence, i, end - 1); } }