乐趣区

关于javascript:码不停题算法篇二叉搜索树的后序遍历序列

题目

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

参考以下这颗二叉搜寻树:

示例 1:

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

示例 2:

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

准备知识点

二叉树的遍历

二叉树的深度优先遍历可细分为前序遍历、中序遍历、后序遍历,这三种遍历能够用递归实现,也可应用非递归实现。

前序遍历:根节点 -> 左子树 -> 右子树(根 -> 左 -> 右)

中序遍历:左子树 -> 根节点 -> 右子树(左 -> 根 -> 右)

后序遍历:左子树 -> 右子树 -> 根节点(左 -> 右 -> 根)

1. 前序遍历

前序的遍历的特点,根节点 -> 左子树 -> 右子树,留神看前序的遍历的代码 printf 语句是放在两条递归语句之前的,所以先 拜访根节点 G,打印 G ,而后拜访左子树 D,此时左子树 D 又作为根节点,打印 D,再拜访 D 的左子树 A

A 又作为根节点,打印 A, A 没有左子树或者右子树,函数调用完结返回到 D 节点(此时曾经打印进去的有:GDA)D 节点的左子树曾经递归实现,当初递归拜访右子树 F,F 作为根节点,打印 F, F 有左子树拜访左子树 E,E 作为

根节点,打印 E,(此时曾经打印进去的有:GDAFE),E 没有左子树和右子树,函数递归完结返回 F 节点,F 的左子树曾经递归实现了,但没有右子树,所以函数递归完结,返回 D 节点,D 节点的左子树和右子树递归全副实现,

函数递归完结返回 G 节点,拜访 G 节点的右子树 M,M 作为根节点,打印 M,拜访 M 的左子树 H,H 作为根节点,打印 H,(此时曾经打印进去的有:GDAFEMH)H 没有左子树和右子树,函数递归完结,返回 M 节点,M 节点的左子树曾经

递归实现,拜访右子树 Z,Z 作为根节点,打印 Z, Z 没有左子树和右子树,函数递归完结,返回 M 节点,M 节点的左子树右子树递归全副实现,函数递归完结,返回 G 节点,G 节点的左右子树递归全副实现,整个二叉树的遍历就完结了

前序遍历后果:GDAFEMHZ

总结一下前序遍历步骤

第一步:打印该节点

第二步:拜访左子树,返回到第一步(留神:返回到第一步的意思是将根节点的左子树作为 新的根节点,就好比图中 D 是 G 的左子树然而 D 也是 A 节点和 F 节点的根节点)

第三步:拜访右子树,返回到第一步

第四步:完结递归,返回到上一个节点

前序遍历的另一种表述:

(1)拜访根节点

(2)前序遍历左子树

(3)前序遍历右子树

(在实现第 2,3 步的时候,也是要依照前序遍历二叉树的规定实现)

2. 中序遍历(具体遍历过程就不再赘述了,(┬_┬))

第一步:拜访该节点左子树

第二步:若该节点有左子树,则返回第一步,否则打印该节点

第三步:若该节点有右子树,则返回第一步,否则完结递归并返回上一节点

(按我本人了解的中序就是:先左到底,左到不能在左了就停下来并打印该节点,而后返回到该节点的上一节点,并打印该节点,而后再拜访该节点的右子树,再左到不能再左了就停下来)

中序遍历的另一种表述:

(1)中序遍历左子树

(2)拜访根节点

(3)中序遍历右子树

(在实现第 1,3 步的时候,要依照中序遍历的规定来实现)

所以该图的中序遍历为:ADEFGHMZ

3. 后序遍历步骤

第一步:拜访左子树

第二步:若该节点有左子树,返回第一步

第三步:若该节点有右子树,返回第一步,否则打印该节点并返回上一节点

后序遍历的另一种表述:

(1)后序遍历左子树

(2)后序遍历右子树

(3)拜访根节点

(在实现 1,2 步的时候,仍然要依照后序遍历的规定来实现)

该图的后序遍历为:AEFDHZMG

网上多找一些重构二叉树的练习题,有助于加深了解上述三种遍历树的过程

重要概念

二叉搜寻树特色:左子树小于根节点小于右子树

题解思路

了解上述知识点后,回顾题目,既然是后序遍历,那么,数组最初一个肯定是根节点,例如给你 [1,3,2,6,5] 这个数组,那么 5 就是根节点,依照二叉搜寻树的特色,1,3 就是左子树,2,6,5 就是右子树。同时每个子树也要满足上诉条件,自然而然就想到递归查找判断了。明确了这些原理后,用代码实现就很容易了。

代码实现

/**
 * @param {number[]} postorder
 * @return {boolean}
 */
var verifyPostorder = function(postorder) {if (!postorder.length) return true; // 如果没有子树了,返回 true
    const root = postorder[postorder.length - 1]; // 后续遍历后果的最初一位是树的根节点
    // 根节点的左子树全副小于根节点,根节点的右子树全副大于根节点
    const leftTree = [], rightTree = []; // 缓存以后节点的左子树和右子树,用于下次递归查问判断
    let cIndex = null; // 记录左右子树的分界点,即第一个满足右子树的节点,因为左右子树要离开递归查
    const flag = postorder.every((item, index) => {if (index === postorder.length - 1) return true; // 根节点不判断
        if (cIndex === null && item > root) {cIndex = index; // 记录第一个遇到大于根节点的右子树节点,作为分界线}
        if (cIndex !== null) { // 如果 cIndex !== null,阐明曾经遍历到右子树的节点了,那就要依照右节点的规定判断接下去的树(右子树的值全都要大于根节点),并且把之后的节点 push 到右子树的数组,用于递归
            if (index >= cIndex) {rightTree.push(item);
                return item > root;
            }
        } else {  // 如果 cIndex === null 就说名没有遇到右子树的节点,那就判断左子树的特色,左子树的节点都要小于根节点
            leftTree.push(item);
            return item < root;
        }
    })
    if (!flag) return false; // 以后节点都没有满足搜寻的特色,那就间接返回 false 了
    let left = true, right = true;
    if (leftTree.length) {left = verifyPostorder(leftTree); // 递归查问判断左子树是否满足二叉搜寻树的特色
    } 
    if (rightTree.length) {right = verifyPostorder(rightTree); // 递归查问判断右子树是否满足二叉搜寻树的特色
    }
    return left && right; // 左右都满足二叉搜寻树的特色,才会返回 true
};
退出移动版