Java,给你二叉树的根节点 root ,返回其节点值 自底向上的层序遍历 。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
时间: 2024-01-05 16:15:36 浏览: 116
好的,这是一道关于二叉树的问题,我来给你讲解一下。
首先,我们需要对二叉树进行层序遍历,这里我们可以使用队列来实现。具体来说,我们可以先将根节点加入队列中,然后不断从队列中取出节点,将其左右子节点加入队列中,直到队列为空。
在进行层序遍历的同时,我们可以记录每个节点所在的层数。具体来说,我们可以使用一个哈希表来记录每个节点的层数,然后在将每个节点加入结果列表时,按照层数的大小将其插入到对应的位置上。这样,最后得到的结果列表就是自底向上的层序遍历。
下面是 Java 实现代码:
```java
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Map<TreeNode, Integer> map = new HashMap<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
map.put(root, 0);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
int level = map.get(node);
if (level == res.size()) {
res.add(0, new ArrayList<>());
}
res.get(0).add(node.val);
if (node.left != null) {
queue.offer(node.left);
map.put(node.left, level + 1);
}
if (node.right != null) {
queue.offer(node.right);
map.put(node.right, level + 1);
}
}
return res;
}
```
这样,我们就完成了这道题目的解答。
阅读全文