vlambda博客
学习文章列表

107. 二叉树的层序遍历 II

力扣题目链接^[1]

给你二叉树的根节点 root ，返回其节点值 「自底向上的层序遍历」 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。

示例1：

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

「提示：」

• 树中节点数目在范围  [0, 2000] 内
• 1000 <= Node.val <= 1000

思路：

本题最终的打印顺序刚好和102题顺序相反，因此不难想到，最后将结果数组反转即可。

BFS+reverse

总体思路和二叉树的层序遍历相同，唯一不同的地方在于将返回的结果进行逆转。「102. 二叉树的层序遍历」的题解可以看这里^[2]。具体的代码逻辑这里就不赘述了。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    let result = [];
    if (!root) return result; // 如果二叉树为空，则返回空数组
    let queue = [root]; // 初始化队列
    while(queue.length) {
        let temp = [];
        let cur = [];
        while(queue.length) { // 遍历每一层节点
            const node = queue.shift();
            cur.push(node.val);
            if (node.left) temp.push(node.left);
            if (node.right) temp.push(node.right);
        }
        result.push(cur); // 每一层节点值组成的数组
        queue = temp; // 将下一层节点信息赋值给队列
    }
    return result.reverse();
};

DFS

那么除了使用队列的形式进行广度优先遍历以外，还有没有其他方案呢？其实是有的。这里也可以使用深度优先遍历进行求解。具体思路如下：

与普通的DFS不同，这里DFS的时候，需要传递第二个参数，用来表明当前节点的层级。递归的时候维护一个二维数组，确保每一层的节点都存在于同一个数组中，这样就达到了层序遍历的目的。

由于默认深度优先遍历是先处理上层节点的，而本题的要求是从下往上，因此跟广度优先遍历的最终处理一样，需要逆转结果数组并返回即可。

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    let result = [];
    const dep = (node, depth) => {
        if (!node) return;
        result[depth] = result[depth] || [];
        result[depth].push(node.val);
        dep(node.left, depth + 1)
        dep(node.right, depth + 1)
    }
    dep(root, 0);
    return result.reverse();
};

总结

本题是二叉树的层序遍历的衍生版本。分别使用了BFS和DFS进行求解。

参考资料