README.md

面试题33. 二叉搜索树的后序遍历序列

题目描述

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

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

     5
    / \
   2   6
  / \
 1   3

示例 1：

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

示例 2：

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

提示：

• 数组长度 <= 1000

解法

二叉搜索树的后序遍历序列是 [左子树, 右子树, 根结点]，且左子树结点值均小于根结点，右子树结点值均大于根结点，递归判断即可。

Python3

class Solution:
    def verifyPostorder(self, postorder: List[int]) -> bool:
        n = len(postorder)
        if n < 2:
            return True
        for i in range(n):
            if postorder[i] > postorder[-1]:
                break
        for j in range(i + 1, n - 1):
            if postorder[j] < postorder[-1]:
                return False
        return (i == 0 or self.verifyPostorder(postorder[:i])) and (i == n - 1 or self.verifyPostorder(postorder[i:-1]))
        

Java

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        if (postorder.length == 0) {
            return true;
        }
        return verifyPostorder(postorder, 0, postorder.length - 1);
    }

    private boolean verifyPostorder(int[] postorder, int from, int to) {
        if (from == to) {
            return true;
        }
        int i = from, j = from;
        for (; i < to; ++i) {
            if (postorder[i] > postorder[to]) {
                break;
            }
        }
        for (j = i + 1; j < to; ++j) {
            if (postorder[j] < postorder[to]) {
                return false;
            }
        }
        return (i == from || verifyPostorder(postorder, from, i - 1)) && (i == to || verifyPostorder(postorder, i, to - 1));


    }
}

JavaScript

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function(postorder) {
    if(!postorder || postorder.length < 2) return true
    let mid = 0
    let root = postorder[postorder.length-1]
    for(let i=0;i<postorder.length-1 && postorder[i] < root;i++) {
        mid++
    }
    for(let i=mid+1;i<postorder.length-1;i++) {
        if(postorder[i] < root) return false
    }
    return verifyPostorder(postorder.slice(0,mid)) && verifyPostorder(postorder.slice(mid+1,postorder.length - 1))
};

...