二叉搜索树的后序遍历序列 2022-03-01 周二

题目

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

学习

JS解法

Java解法

分析

• 后序遍历定义： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。

• 二叉搜索树定义： 左子树中所有节点的值 << 根节点的值；右子树中所有节点的值 >> 根节点的值；其左、右子树也分别为二叉搜索树。

后续遍历

• 二叉搜索树后续遍历用数组表示，最后一个元素就是root
  剩下的，以root为标准，分为左子树（都 < root）和右子树（都 > root）

• 递归：左子树和右子树仍然是二叉搜索树。

思路

• JS中Array的pop就是取出最后一个元素，也就是root；同时root也取出了，只剩下左右子树了。

• 以root为标准，从0号元素开始比较，小于root的都是属于左子树，剩下的事又子树。JS中Array的slice方法可以分开左右子树。

• 左子树已经检查过，剩下的右子树遍历检查一下，要求都大于root

• 递归：将上面的过程继续在左右子树重复做

• 退出条件：数组元素个数少于3个；

比如两个元素，那么第2个元素就是root；
第1个元素如果< root，那么就可以认为是左子树；
第1个元素如果> root，那么就可以认为是右子树；

JS代码

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function(postorder) {
    // 退出条件，元素个数不足3个，必然符合条件
    if (postorder.length < 3) {
        return true;
    }

    // 取出判断标准root，也就是最后一个元素
    let root = postorder.pop();

    // 找出左右子树的分界点; i的左边（不包括i）是左子树；i的右边（包括i）是右子树
    let i = 0;
    while (postorder[i] < root) {
        i++;
    }

    // 以i为界限（i属于右子树），分为左右子树
    let leftTree = postorder.slice(0, i); // 刚好，i不包括
    let rightTree = postorder.slice(i); // 刚好，i包括在内

    // 左子树不用查，检查右子树
    let rightResult = rightTree.every(
        (item) => {
            return item > root;
        }
    );
    
    // 如果右子树不对，直接返回FALSE，剩下的就不用查了；
    if (!rightResult) {
        return false;
    }

    // 继续查左右子树，并且要求两者都要正确
    return (verifyPostorder(leftTree) && verifyPostorder(rightTree));
};

备注

JS不查类型，用起来很灵活；但是同样地，也很容易犯错。比如 if (!rightResult) 这个地方错误写成了 if (!rightTree) ，就很难查出问题。（很多用例可以过）

错误结果 错误代码之处