陕西网站建设设计公司301跳转wordpress

当前位置： 首页 > news >正文

陕西网站建设设计公司,301跳转wordpress,谷城网站制作,logo设计在线生成免费版层序遍历 题目详细#xff1a;LeetCode.102 层序遍历与上一节讲的三种遍历方式有所不同#xff0c;层序遍历是指按从上到下#xff0c;从左到右的顺序#xff0c;逐层地遍历二叉树的节点。 从其节点的遍历顺序上观察#xff0c;我们可以发现其跟广度优先遍历#xff0…层序遍历 题目详细LeetCode.102 层序遍历与上一节讲的三种遍历方式有所不同层序遍历是指按从上到下从左到右的顺序逐层地遍历二叉树的节点。 从其节点的遍历顺序上观察我们可以发现其跟广度优先遍历BFS的遍历思想非常相似既然我们可以利用队列先进先出的特点来实现广度优先遍历那么我们也可以用队列来实现对二叉树的层序遍历 定义一个二维数组其下标表示第i层数组元素则存储着每一层遍历的节点定义一个队列利用其先进先出的特点先将非空的根节点进队定义一个循环遍历入队的二叉树节点 定义一个变量记录每一层的节点数目也就是当前队列的长度定义一个循环获取变量得知在第一层只有根节点一个节点 那么我们只需要出队一次将根节点出队队列长度 - 1定义一个一维数组存放该层的节点值并将该数组追加入到二维数组中然后将其非空的左右节点依次进队循环直到该层的节点都遍历完毕 循环直到队列为空说明二叉树层序遍历完成 Java解法队列BFS class Solution {public ListListInteger ans new ArrayList();public ListListInteger levelOrder(TreeNode root) {this.bfs(root);return ans;}public void bfs(TreeNode root){QueueTreeNode queue new LinkedList();if(null ! root) queue.offer(root);while(!queue.isEmpty()){int n queue.size();ListInteger floor new ArrayList();while(n– 0){TreeNode node queue.poll();floor.add(node.val);if(null ! node.left) queue.offer(node.left);if(null ! node.right) queue.offer(node.right);}ans.add(floor);}} }这道题我们可以模拟层序遍历的思想利用递归来解题只需要在递归函数中增加一个变量记录节点是第几层的即可 Java解法模拟递归 class Solution {public ListListInteger ans new ArrayList();public ListListInteger levelOrder(TreeNode root) {this.order(root, 0);return ans;}public void order(TreeNode root, int level){if(null root) return;if(level ans.size() - 1){ListInteger floor new ArrayList();floor.add(root.val);ans.add(floor);}else{ans.get(level).add(root.val);}this.order(root.left, level 1); this.order(root.right, level 1); } }学会了二叉树的层序遍历后可以一口气打完以下十道LeetCode题 102.二叉树的层序遍历 104.二叉树的最大深度 107.二叉树的层次遍历II 111.二叉树的最小深度 116.填充每个节点的下一个右侧节点指针 117.填充每个节点的下一个右侧节点指针II 199.二叉树的右视图 429.N叉树的层序遍历 515.在每个树行中找最大值 637.二叉树的层平均值 翻转二叉树 题目详细LeetCode.226 翻转二叉树的过程和结果 观察上图动画我们可以发现上图采用的是层序遍历的顺序在遍历的过程中将每个节点的左右节点进行交换这就是翻转二叉树的解题思想。 所以想要解题很简单就是采用合适的遍历方法在访问节点的时候将其左右节点进行交换即可 需要注意的是在这道题中我们采用的遍历二叉树方法一般是前序遍历、后序遍历和层序遍历因为采用中序遍历的方式会导致重复交换子节点需要在遍历过程中加以逻辑判断才能避免这一情况不易编写和理解。 如何遍历在这里就不作赘述了不了解的可以查看上一节的内容详细讲述了遍历二叉树的各种方法【Day14】传送门 Java解题递归前序遍历 class Solution {public TreeNode invertTree(TreeNode root) {this.invertPre(root);return root;}public void swapChildNode(TreeNode node){TreeNode temp node.left;node.left node.right;node.right temp;}public void invertPre(TreeNode root){if(null root) return;this.swapChildNode(root);this.invertPre(root.left);this.invertPre(root.right);} }Java解题统一迭代前序遍历 class Solution {public TreeNode invertTree(TreeNode root) {this.invertPre(root);return root;}public void swapChildNode(TreeNode node){TreeNode temp node.left;node.left node.right;node.right temp;}public void invertPre(TreeNode root){StackTreeNode stack new Stack();if(null ! root) stack.push(root);while(!stack.isEmpty()){// 标记节点TreeNode tagNode stack.peek();if(tagNode ! null){// 非标记节点先弹出在需要处理的节点后追加空指针作为标记仅作标记不作处理TreeNode node stack.pop();if(null ! node.right) stack.push(node.right);if(null ! node.left) stack.push(node.left);stack.push(node);stack.push(null);}else{// 遇到标记节点先弹出作为标记的空指针的节点再处理数据处理节点不作标记stack.pop();TreeNode node stack.pop();this.swapChildNode(node);}}} }对称二叉树 题目详细LeetCode.101 由题可知判断一棵二叉树是否对称 根节点无需比较接着比较树的内侧的节点和外侧的节点而不是比较树的左右节点当每棵子树都满足内侧节点相等外侧节点相等那么则称这整棵二叉树是对称的 所以关键在于如何遍历二叉树以及如何比较树的内侧节点和外侧节点。 既然根节点不需要比较那么我们就需要同时比较其左右两棵子树上的节点在比较过程中会出现四种情况 左右节点皆为空则是对称的左右节点只有一个为空则是不对称的左右节点皆不为空但是他们的值不相等是不对称的左右节点皆不为空但是他们的值相等是对称的 所以对于每一棵子树我们只需要按照上述情况去比较其内侧和外侧节点就可以得到正确答案 树的内侧节点选左子树的右节点和右子树的左节点进行比较树的外侧节点选左子树的左节点和右子树的右节点进行比较当出现一种不对称情况时则整个树是不对称的无需继续比较当出现对称情况时继续比较剩余的左右子树 Java解题递归 class Solution {public boolean isSymmetric(TreeNode root) {return this.check(root.left, root.right);}public boolean check(TreeNode leftNode, TreeNode rightNode){if(null leftNode null rightNode) return true;else if(null leftNode || null rightNode || leftNode.val ! rightNode.val) return false;return check(leftNode.right, rightNode.left) check(leftNode.left, rightNode.right);} }Java解题迭代队列 class Solution {public QueueTreeNode queue new LinkedList();public boolean isSymmetric(TreeNode root) {return this.check(root.left, root.right);}public boolean check(TreeNode leftNode, TreeNode rightNode){this.queue.offer(leftNode);this.queue.offer(rightNode);while(!queue.isEmpty()){leftNode queue.poll();rightNode queue.poll();if(null leftNode null rightNode)continue;else if(null leftNode || null rightNode || leftNode.val ! rightNode.val){return false; this.queue.offer(leftNode.right);this.queue.offer(rightNode.left);this.queue.offer(leftNode.left);this.queue.offer(rightNode.right);}return true;} }观察代码以及二叉树的遍历过程我们也可以发现对于对称二叉树的遍历顺序左子树的遍历顺序是右左根而右子树的遍历顺序是左右根两者都属于后序遍历也就是说这道题是基于后序遍历来解决的。 除了在二叉树中常用的递归方法外我们还可以结合前面学习的其他数据结构如栈和队列也能够辅助我们遍历和处理二叉树。 最后这两天做二叉树相关的题目之后给我的感触就是二叉树的题目千变万化但是总结起来就是两个要点选择最佳的遍历顺序 处理节点的需求逻辑可见解答二叉树相关的题目时理解和掌握二叉树不同的遍历思想是尤其重要的 水之积也不厚则其负大舟也无力。