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

Lin2J
2021-07-21 / 0 评论 / 80 阅读
温馨提示:
本文最后更新于2021-07-21,若内容或图片失效,请留言反馈。

剑指 Offer 33. 二叉搜索树的后序遍历序列

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

解题思路:

后序遍历的定义:【左子树 | 右子树 | 根节点】

二叉搜索树定义:左子树中所有节点值 $<$ 根节点的值;右子树中所有节点的值 $>$ 根节点的值;其左右子树也为二叉搜索树。

根据以上两个定义,可以得到如下结论:

  1. 拿到序列最后一个元素的值 $x$ ,可以将序列分为左子树和右子树。其中,小于 x 的连续元素的集合为左子树的序列;大于 x 的连续元素的结合为右子树的序列。
  2. 左子树的序列和右子树的序列同样满足结论 $1$。

根据以上的结论,可以使用一个指针 $p$ 和 $m$。$p$ 指向的元素会与 $x$ 进行对比,$m$ 记录的是左子树的右边界(不包含 $m$)。

验证函数

**参数传递:**后序遍历数组 $postorder$,数组的左右边界(包含)$l$、$r$。

终止条件: $l$ 大于等于 r 时,返回 $true$。

递推工作:

  1. $p$ 指针指向 $l$,$x$ 为 $postorder[r]$ 的值
  2. 循环检查:如果 $p$ 指向的元素小于 $x$,说明该元素属于左子树,$p$ 自增。
  3. 用 $m$ 记录 $p$ 的值,此时 $[l, m-1]$ 区间为左子树。
  4. 循环检查:如果 $p$ 指向的元素大于 $x$,说明该元素属于右子树,$p$ 自增。
  5. 通过以上两个循环,对于合法的序列,此时应该有 $p = r$,然后分别对左子树区间 $[l, m-1]$ 和右子树区间 $[m, r-1]$ 进行下一层的递归,返回递归结果。

代码:

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

private boolean verifyPostOrder(int[] postOrder, int l, int r) {
    if (l >= r) {
        return true;
    }
    int p = l;
    while (postOrder[p] < postOrder[r]) {
        p++;
    }
    // [l,m) 为左子树
    int m = p;
    while (postOrder[p] > postOrder[r]) {
        p++;
    }
    // 如果是合法的后序遍历,那么此时 p == r
    return p == r && verifyPostOrder(postOrder, l, m - 1) && verifyPostOrder(postOrder, m, r - 1);
}

复杂度分析

  • 时间复杂度$O(N^2)$:$N$ 为序列的长度。验证函数每一层只会去掉一个根节点,因此递归占用 $O(N)$。最坏情况下,树退化成链表,每一层占用的时间为 $O(N)$ 。

  • 空间复杂度$O(N)$:$N$ 为序列的长度。最差情况下,树退化成链表,递归深度达到 $N$。

大佬解法