基础知识(青铜挑战)
-
了解二叉树的基础知识
实战训练(白银挑战)
简单的层序遍历
-
基本的层序遍历思路很清晰:
-
给你一个二叉树根节点,你需要创建一个队列 queue 来遍历节点,一个链表 list 来存储节点的数据域,即值
-
首先将根节点入队
-
队列 queue 出队,将该节点值存入 list,再依次将左右孩子节点入队
-
重复以上操作,每个节点出对后,都存储该节点值到 list 中,再依次将左右孩子节点入队,直到队列 queue为空
-
这样得到的数据链表 list 就是按层序遍历的顺序得到的
-
-
具体代码如下:(2023/09/09午)
public static List<Integer> simpleLevelOrder(TreeNode root) {if (root == null) {return new ArrayList<Integer>();}
List<Integer> res = new ArrayList<Integer>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点放入队列中,然后不断遍历队列queue.add(root);//有多少元素执行多少次while (queue.size() > 0) {//获取当前队列的长度,这个长度相当于 当前这一层的节点个数TreeNode t = queue.remove();res.add(t.val);if (t.left != null) {queue.add(t.left);}if (t.right != null) {queue.add(t.right);}}return res;}
层序遍历分层
-
层序遍历我们做到了,这里添加一个要求:对层序遍历的节点值分层处理,即二叉树每层的节点值分别存放进一个链表 list 中
-
这个代码怎么写呢?很简单的,按这个思路走:
-
我们之前层序遍历时,每出队一个节点,都把其值存入 list 链表中,然后入队其孩子节点
-
在开始出队某一层的节点时,此时队列的节点数,就是二叉树这一层的节点数
-
那我们根据可以某时刻队列容量来遍历队列,将这层的节点全部出队,并且把节点值存入该层独有的 list 中
-
当然了,每个节点出队后,要将自己的孩子节点依次入队
-
这样,当队列为空时,我们得到了各层的节点链表 list,返回一个包含各层 list 的 list 即可
-
-
具体代码如下:(2023/09/09晚)
public static List<List<Integer>> level102Order(TreeNode root) {if (root == null) {return new ArrayList<List<Integer>>();}
List<List<Integer>> res = new ArrayList<List<Integer>>();LinkedList<TreeNode> queue = new LinkedList<TreeNode>();//将根节点放入队列中,然后不断遍历队列queue.add(root);while (queue.size() > 0) {//获取当前队列的长度,这个长度相当于 当前这一层的节点个数int size = queue.size();ArrayList<Integer> tmp = new ArrayList<Integer>();//将队列中的元素都拿出来(也就是获取这一层的节点),放到临时list中//如果节点的左/右子树不为空,也放入队列中for (int i = 0; i < size; ++i) {TreeNode t = queue.remove();tmp.add(t.val);if (t.left != null) {queue.add(t.left);}if (t.right != null) {queue.add(t.right);}}//将临时list加入最终返回结果中res.add(tmp);}return res;}
自底向上的层序遍历
-
在前面学习的基础上,实现这个要求就很简单了
-
在拿到各层节点值的 list 后,按头插的方式,插入链表 list 中,就实现了自底向上的层序遍历了(2023/09/09晚)
-
具体代码如下:
public static List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();if (root == null) {return levelOrder;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();int size = queue.size();for (int i = 0; i < size; i++) {TreeNode node = queue.poll();level.add(node.val);TreeNode left = node.left, right = node.right;if (left != null) {queue.offer(left);}if (right != null) {queue.offer(right);}}levelOrder.add(0, level);//栈}return levelOrder;}