107. 二叉树的层序遍历 II
107. 二叉树的层序遍历 II
🟠 🔖 树
广度优先搜索
二叉树
🔗 力扣
LeetCode
题目
Given the root
of a binary tree, return the bottom-up level order traversal of its nodes ' values. (i.e., from left to right, level by level from leaf to root).
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]
. -1000 <= Node.val <= 1000
题目大意
给你二叉树的根节点 root
,返回其节点值 自底向上的层序遍历 。(即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)。
解题思路
这道题与 第 102 题 的解题思路相同,区别在于返回数组的顺序要求自底向上。
可以使用广度优先遍历(BFS)实现,注意每层的节点从数组前端插入即可。
- 首先将根节点放入队列中;
- 更新队列的长度
len
,遍历队列的前len
个节点; - 如果该节点存在直接子节点,将直接子节点加入队列中,并将节点的值存入一个临时数组中;
- 将队列的前
len
个节点出队,此时队列中都是下一层的子节点,将临时数组加入返回值中; - 重复步骤 2、3、4,直至队列为空;
代码
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrderBottom = function (root) {
let res = [];
if (!root) return res;
let queue = [root];
while (queue.length) {
let len = queue.length;
let temp = [];
for (let i = 0; i < len; i++) {
if (queue[i].left) queue.push(queue[i].left);
if (queue[i].right) queue.push(queue[i].right);
temp.push(queue[i].val);
}
res.unshift(temp);
queue = queue.slice(len);
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
102 | 二叉树的层序遍历 | [✓] | 树 广度优先搜索 二叉树 | |
637 | 二叉树的层平均值 | [✓] | 树 深度优先搜索 广度优先搜索 1+ |