力扣题目链接[1]
给你二叉树的根节点 root
,返回其节点值 「自底向上的层序遍历」 。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)。
示例1:
输入:root = [3,9,20,null,null,15,7]
输出:[[15,7],[9,20],[3]]
「提示:」
[0, 2000]
内1000 <= Node.val <= 1000
思路:
本题最终的打印顺序刚好和102题顺序相反,因此不难想到,最后将结果数组反转即可。
总体思路和二叉树的层序遍历相同,唯一不同的地方在于将返回的结果进行逆转。「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的时候,需要传递第二个参数,用来表明当前节点的层级。递归的时候维护一个二维数组,确保每一层的节点都存在于同一个数组中,这样就达到了层序遍历的目的。
由于默认深度优先遍历是先处理上层节点的,而本题的要求是从下往上,因此跟广度优先遍历的最终处理一样,需要逆转结果数组并返回即可。
/**
* @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