网站制作建设兴田德,公司介绍简介,新网站建设银行提升转账额度,酒店网站模版基础知识#xff08;青铜挑战#xff09; 了解二叉树的基础知识
实战训练#xff08;白银挑战#xff09;
简单的层序遍历 基本的层序遍历思路很清晰#xff1a; 给你一个二叉树根节点#xff0c;你需要创建一个队列 queue 来遍历节点#xff0c;一个链表 list 来存储…基础知识青铜挑战 了解二叉树的基础知识
实战训练白银挑战
简单的层序遍历 基本的层序遍历思路很清晰 给你一个二叉树根节点你需要创建一个队列 queue 来遍历节点一个链表 list 来存储节点的数据域即值 首先将根节点入队 队列 queue 出队将该节点值存入 list再依次将左右孩子节点入队 重复以上操作每个节点出对后都存储该节点值到 list 中再依次将左右孩子节点入队直到队列 queue为空 这样得到的数据链表 list 就是按层序遍历的顺序得到的 具体代码如下2023/09/09午
public static ListInteger simpleLevelOrder(TreeNode root) {if (root null) {return new ArrayListInteger();}
ListInteger res new ArrayListInteger();LinkedListTreeNode queue new LinkedListTreeNode();//将根节点放入队列中然后不断遍历队列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 ListListInteger level102Order(TreeNode root) {if (root null) {return new ArrayListListInteger();}
ListListInteger res new ArrayListListInteger();LinkedListTreeNode queue new LinkedListTreeNode();//将根节点放入队列中然后不断遍历队列queue.add(root);while (queue.size() 0) {//获取当前队列的长度这个长度相当于 当前这一层的节点个数int size queue.size();ArrayListInteger tmp new ArrayListInteger();//将队列中的元素都拿出来(也就是获取这一层的节点)放到临时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 ListListInteger levelOrderBottom(TreeNode root) {ListListInteger levelOrder new LinkedListListInteger();if (root null) {return levelOrder;}QueueTreeNode queue new LinkedListTreeNode();queue.offer(root);while (!queue.isEmpty()) {ListInteger level new ArrayListInteger();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;}
