本文共 1363 字，大约阅读时间需要 4 分钟。

二叉搜索树后序遍历序列验证

后序遍历与二叉搜索树定义

后序遍历（Postorder Traversal）是指遍历树的顺序为“左、右、根”。在二叉搜索树（Binary Search Tree, BST）中，这种遍历方式能够验证某个序列是否为二叉搜索树的后序遍历。根据定义：

通过递归的方式，可以验证所有子树的正确性（即其后序遍历是否满足二叉搜索树定义）。若所有子树都正确，则该序列即为二叉搜索树的后序遍历。

递归解析

递归函数 recur(postorder, i, j) 用于验证给定区间 [i, j] 是否为二叉搜索树的后序遍历序列。以下是递归逻辑：

终止条件

当 i >= j 时，说明此子树节点数量≤1，无需判别正确性，直接返回 true。

递推工作

递归实现

boolean recur(int[] postorder, int i, int j) {    if (i >= j) {        return true;    }    int p = i;    // 找到第一个大于根节点的值的索引    while (postorder[p] < postorder[j]) {        p++;    }    int m = p;    // 找到第一个等于或大于根节点的值的索引    while (postorder[p] > postorder[j]) {        p++;    }    // 判断根节点是否正确，左子树和右子树是否正确    return p == j && recur(postorder, i, m - 1) && recur(postorder, m, j - 1);}

测试示例

@Testpublic void test() {    boolean b = verifyPostorder(new int[]{1, 3, 2, 6, 5});}

复杂度分析

时间复杂度

• O(N^2)：每次递归调用 recur(i, j) 减去一个根节点，最坏情况下（树退化为链表）每轮递归都需要遍历所有节点。

空间复杂度

• O(N)：最坏情况下（树退化为链表），递归深度达到 N。

代码解释

上述代码实现了后序遍历序列的验证逻辑。通过递归划分左右子树并验证其正确性，确保所有子树都符合二叉搜索树的定义。

转载地址：http://blhfk.baihongyu.com/