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

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

示例：

输入: [1,3,2,5,7,6,4]
输出: True

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

解题思路

核心思想：利用二叉搜索树的特性：左子树所有节点 < 根节点 < 右子树所有节点。

关键步骤：

1. 后序遍历的最后一个元素是根节点
2. 从前往后找第一个大于根节点的位置，分割左右子树
3. 检查右子树是否都大于根节点
4. 递归验证左右子树

时间复杂度：O(n^2) 最坏，平均O(n log n) 空间复杂度：O(n)

Python 实现

def verify_squence_of_bst(sequence):
    """
    判断序列是否是二叉搜索树的后序遍历

    Args:
        sequence: 待验证的序列

    Returns:
        bool: 是否合法
    """
    if not sequence:
        return False

    def verify(seq, start, end):
        if start >= end:
            return True

        root = seq[end]  # 最后一个元素是根节点

        # 找到左子树的结束位置
        i = start
        while i < end and seq[i] < root:
            i += 1

        # 检查右子树是否都大于根节点
        j = i
        while j < end:
            if seq[j] < root:
                return False
            j += 1

        # 递归验证左右子树
        return verify(seq, start, i - 1) and verify(seq, i, end - 1)

    return verify(sequence, 0, len(sequence) - 1)


# 测试代码
if __name__ == "__main__":
    test_cases = [
        [1, 3, 2, 5, 7, 6, 4],  # True
        [1, 6, 3, 2, 5],         # False
        [1, 2, 3, 4, 5],         # True
        [],                       # False
    ]

    for seq in test_cases:
        print(f"{seq} → {verify_squence_of_bst(seq)}")

# 输出:
# [1, 3, 2, 5, 7, 6, 4] → True
# [1, 6, 3, 2, 5] → False
# [1, 2, 3, 4, 5] → True
# [] → False

图解

示例: [1,3,2,5,7,6,4]

后序遍历特征:
- 最后一个元素4是根节点
- 左子树: [1,3,2] (都小于4)
- 右子树: [5,7,6] (都大于4)

验证左子树 [1,3,2]:
- 最后一个元素2是根节点
- 左子树: [1] (都小于2)
- 右子树: [3] (都大于2)
- 继续...

验证右子树 [5,7,6]:
- 最后一个元素6是根节点
- 左子树: [5] (都小于6)
- 右子树: [7] (都大于6)
- 继续...

最终返回True