临沂高端网站建设,立网站系,高端品牌网站建设策略,手工制作图片作品随想录日记part13 t i m e #xff1a; time#xff1a; time#xff1a; 2024.03.06 主要内容#xff1a;今天的主要内容是二叉树的第二部分哦#xff0c;主要有层序遍历#xff1b;翻转二叉树#xff1b;对称二叉树。 102.二叉树的层序遍历226.翻转二叉树101. 对称二叉…随想录日记part13 t i m e time time 2024.03.06 主要内容今天的主要内容是二叉树的第二部分哦主要有层序遍历翻转二叉树对称二叉树。 102.二叉树的层序遍历226.翻转二叉树101. 对称二叉树 Topic1二叉树的层序遍历
题目 给你二叉树的根节点 r o o t root root 返回其节点值的层序遍历。 即逐层地从左到右访问所有节点。
示例 输入 r o o t [ 3 , 9 , 20 , n u l l , n u l l , 15 , 7 ] root [3,9,20,null,null,15,7] root[3,9,20,null,null,15,7] 输出 [ [ 3 ] , [ 9 , 20 ] , [ 15 , 7 ] ] [[3],[9,20],[15,7]] [[3],[9,20],[15,7]]
**思路**层序遍历是一层一层去遍历二叉树符合先进先出的规则即图论中的广度优先遍历思路所以这道题目我们需要辅助的队列来实现层序遍历。其遍历的动画可以观看下面的动画 下面给出两种层序遍历的写法
class Solution {// 定义一个记录组后输出的数组public ListListInteger resList new ArrayListListInteger();public ListListInteger levelOrder(TreeNode root) {//levelOrder_queue(root);levelOrder_queue_pro(root,0);return resList;}// 使用栈辅助进行层次遍历private void levelOrder_queue(TreeNode root) {if (root null)return;// 创建辅助队列QueueTreeNode q new LinkedListTreeNode();q.offer(root);while (!q.isEmpty()) {ListInteger tem new ArrayListInteger();int length q.size();while (length 0) {TreeNode t q.poll();tem.add(t.val);if (t.left ! null)q.offer(t.left);if (t.right ! null)q.offer(t.right);length--;}resList.add(tem);}}//使用递归的方法private void levelOrder_queue_pro(TreeNode root,int deep){if(rootnull) return;deep;if(resList.size()deep){//当层级增加时list的Item也增加利用list的索引值进行层级界定ListInteger tem new ArrayListInteger();resList.add(tem);}resList.get(deep-1).add(root.val);levelOrder_queue_pro(root.left,deep);levelOrder_queue_pro(root.right,deep);}
}上面的两种写法务必要记住。 Topic2翻转二叉树
**题目**给你一棵二叉树的根节点 r o o t root root 翻转这棵二叉树并返回其根节点。 示例 输入 r o o t [ 4 , 2 , 7 , 1 , 3 , 6 , 9 ] root [4,2,7,1,3,6,9] root[4,2,7,1,3,6,9] 输出 [ 4 , 7 , 2 , 9 , 6 , 3 , 1 ] [4,7,2,9,6,3,1] [4,7,2,9,6,3,1]
**思路**整个树的翻转主要有两种思路
递归迭代 递归法写好递归是要有三个关键点注意的 1.确定参数和返回值 TreeNode transTree(TreeNode root);2.确定中止条件 if(rootnull)return null;3.确定单层递归逻辑 我的代码是前序遍历先反转左右子树然后进行交换左右孩子节点 TreeNode btransTree(root.right);TreeNode atransTree(root.left);tem.leftb;tem.righta;完整的 j a v a java java 代码如下
class Solution {public TreeNode invertTree(TreeNode root) {return transTree(root);}private TreeNode transTree(TreeNode root) {TreeNode tem root;if (tem null)return null;TreeNode b transTree(root.right);TreeNode a transTree(root.left);tem.left b;tem.right a;return root;}
}迭代法能够使用递归的方法都能使用栈来实现 如下面代码实现 class Solution {public TreeNode invertTree(TreeNode root) {if(rootnull)return root;//建立栈StackTreeNode stacknew StackTreeNode();stack.push(root);while(!stack.isEmpty()){TreeNode temstack.pop();transpoint(tem);if(tem.right!null)stack.push(tem.right);if(tem.left!null)stack.push(tem.left);}return root;}private void transpoint(TreeNode root){if(rootnull)return;else{TreeNode troot.left;root.leftroot.right;root.rightt;}}
}Topic3对称二叉树
**题目**给你一个二叉树的根节点 r o o t root root 检查它是否轴对称。 示例 输入 r o o t [ 1 , 2 , 2 , 3 , 4 , 4 , 3 ] root [1,2,2,3,4,4,3] root[1,2,2,3,4,4,3] 输出 t r u e true true
思路 后序遍历的递归法以及迭代法 递归法 class Solution {// 递归法public boolean isSymmetric(TreeNode root) {if (root null)return true;elsereturn isSame(root.left, root.right);}private boolean isSame(TreeNode left, TreeNode right) {if (left null right ! null)return false;else if (left ! null right null)return false;else if (left null right null)return true;else {boolean a isSame(left.left, right.right);boolean b isSame(left.right, right.left);return (a b);}}
}迭代法 代码实现如下 class Solution {// 使用队列辅助实现的迭代法public boolean isSymmetric(TreeNode root) {if (root null)return true;DequeTreeNode queue new LinkedList();queue.offerFirst(root.left);// 将左子树头节点压入queue.offerLast(root.right);// 将右子树头节点压入while (!queue.isEmpty()) {TreeNode left queue.pollFirst();TreeNode right queue.pollLast();if (left null right null)continue;if (left null || right null || left.val ! right.val)return false;queue.offerFirst(left.left);queue.offerLast(right.right);queue.offerFirst(left.right);queue.offerLast(right.left);}return true;}
}
