题目
107. 二叉树的层序遍历 II
分析
这个题目考查的是二叉树的层序遍历,对于二叉树的层序遍历,我们需要借助 队列 这种数据结构。再来回归本题 ,我们只需要将 二叉树的层序遍历的结果逆序,就可以得到这道题我们要求的答案了。接下来我们的难题就是如何实现二叉树的层序遍历了。
以例一为例子:
这个二叉树的层序遍历为 [ [3] , [9,20] , [15,7] ]。
怎么实现呢?
首先将根节点放入队列,判断队列是否为空,如果不为空记录当前队列的元素个数(这个个数就是这一层的所有元素),借助一个中间容器存放当前层的元素list,遍历这一层的所有元素放入list中,并且将这一层每一个元素的左右孩子如果不为空放入队列里面。
下面画图展示一下:
文章来源:https://www.toymoban.com/news/detail-831391.html
代码
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
while(size != 0) {
size--;
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(list);
}
Collections.reverse(res);
return res;
}
}
文章来源地址https://www.toymoban.com/news/detail-831391.html
到了这里,关于LeetCode.107. 二叉树的层序遍历 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!