107. 二叉树的层序遍历 II
力扣题目链接[1]
给你二叉树的根节点 root ，返回其节点值 「自底向上的层序遍历」 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）。
示例1：
代码语言：javascript复制输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
「提示：」
- 树中节点数目在范围
[0, 2000]内 1000 <= Node.val <= 1000
思路：
本题最终的打印顺序刚好和102题顺序相反，因此不难想到，最后将结果数组反转即可。
BFS reverse
总体思路和二叉树的层序遍历相同，唯一不同的地方在于将返回的结果进行逆转。「102. 二叉树的层序遍历」的题解可以看这里[2]。具体的代码逻辑这里就不赘述了。
代码语言：javascript复制/**
* 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的时候，需要传递第二个参数，用来表明当前节点的层级。递归的时候维护一个二维数组，确保每一层的节点都存在于同一个数组中，这样就达到了层序遍历的目的。
由于默认深度优先遍历是先处理上层节点的，而本题的要求是从下往上，因此跟广度优先遍历的最终处理一样，需要逆转结果数组并返回即可。
代码语言：javascript复制/**
* @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进行求解。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
[2]
这里: https://juejin.cn/post/7089448779140726791
