网站建设 英语翻译,修改网站源码连接数据库怎么做,十堰秦楚网最新消息十堰秦,三亚发布最新消息一、二叉树的层序遍历
题目#xff1a;
给你二叉树的根节点 root #xff0c;返回其节点值的 层序遍历 。 #xff08;即逐层地#xff0c;从左到右访问所有节点#xff09;。
示例 1#xff1a; 输入#xff1a;root [3,9,20,null,null,15,7]
输出#xff1a;[[3]…一、二叉树的层序遍历
题目
给你二叉树的根节点 root 返回其节点值的 层序遍历 。 即逐层地从左到右访问所有节点。
示例 1 输入root [3,9,20,null,null,15,7]
输出[[3],[9,20],[15,7]]示例 2
输入root [1]
输出[[1]]示例 3
输入root []
输出[] 思路
用队列来存储元素变量size来存储每一层的元素个数扫描队头元素判断其是否有左右孩子如果有将其入队同时该队头元素出队记录在该层所封装的结果集中同时size减一当size值减为0时说明该层所有元素均遍历完毕返回结果集
代码
// 结果列表用于存储每一层的节点值列表
public ListListInteger resList new ArrayListListInteger();// 主方法进行二叉树的层次遍历
public ListListInteger levelOrder(TreeNode root) {// 调用辅助方法进行层次遍历test(root);// 返回结果列表return resList;
}// 辅助方法实现二叉树的层次遍历
public void test(TreeNode root) {// 如果根节点为空直接返回if (root null)return;// 创建队列用于存储待处理的节点QueueTreeNode queue new LinkedList();queue.add(root); // 将根节点加入队列// 循环处理队列中的节点直到队列为空while (!queue.isEmpty()) {// 用于存储当前层节点值的列表ListInteger list new LinkedList();int len queue.size(); // 当前层节点的数量// 处理当前层的所有节点while (len 0) {TreeNode tnode queue.poll(); // 出队列获取当前处理的节点list.add(tnode.val); // 将节点值加入当前层的列表// 将当前节点的左右子节点加入队列用于下一层处理if (tnode.left ! null)queue.add(tnode.left);if (tnode.right ! null)queue.add(tnode.right);len--; // 当前层节点数减一}// 将当前层的节点值列表加入结果列表resList.add(list);}
}resList 定义和初始化 public ListListInteger resList new ArrayListListInteger();定义了一个成员变量 resList用于存储二叉树的层次遍历结果。初始化为空的 ArrayList用于存储每一层的节点值列表。 levelOrder 方法 public ListListInteger levelOrder(TreeNode root)主方法调用 test 方法进行二叉树的层次遍历并返回最终的层次遍历结果 resList。 test 方法 public void test(TreeNode root)辅助方法实现二叉树的层次遍历。使用队列 queue 进行广度优先搜索BFS 首先将根节点加入队列。每次处理队列中的一个节点将其值加入当前层的 list 中并将其左右子节点如果存在加入队列。每处理完一层的所有节点后将当前层的节点值列表 list 加入 resList 中。 二、翻转二叉树
题目
给你一棵二叉树的根节点 root 翻转这棵二叉树并返回其根节点。
示例 1 输入root [4,2,7,1,3,6,9]
输出[4,7,2,9,6,3,1]示例 2 输入root [2,1,3]
输出[2,3,1]示例 3
输入root []
输出[]思路
可以采用递归前序和后序遍历的方法遍历一个结点的同时反转其左右子节点接着往下一层移动重复以上操作直到遍历到的节点为空停止
代码
//前序
public TreeNode invertTree(TreeNode root) {if (root null)return root;swap(root); // 调用 swap 方法交换当前节点的左右子节点 中invertTree(root.left); // 递归翻转左子树 左invertTree(root.right); // 递归翻转右子树 右return root; // 返回翻转后的根节点
}
public void swap(TreeNode root) {TreeNode temp root.left;root.left root.right;root.right temp;
}后序遍历方法类似只需将顺序修改为左右中即可
用中序遍历的方法稍有不同由于中序是左中右的顺序当返回到根节点时左右子树交换顺序此时应该继续遍历右子树但是这时的右子树正好是刚刚交换完的左子树 因此实际上仅是交换了一次左子树要想实现反转必须再次进行左子树的交换操作即可代码如下
invertTree(root.left); // 递归翻转左子树 左
swap(root); // 调用 swap 方法交换当前节点的左右子节点 中
invertTree(root.left); // 这时再次操作反转后的左子树 右 三、对称二叉树
题目
给你一个二叉树的根节点 root 检查它是否轴对称。
示例 1 输入root [1,2,2,3,4,4,3]
输出true示例 2 输入root [1,2,2,null,3,null,3]
输出false
思路
采用后序遍历的方法为什么要采用后序呢由于后序遍历的顺序是左右中而要判断二叉树是否对称就是要判断根节点的左右子树是否在翻转后可以重合后序的遍历顺序正好可以判断左右子树再在最后遍历根节点具体方法是先遍历根节点的左右子节点是否相同再判断左子节点的左子节点是否与右子节点的右子节点相同同理再判断左子节点的右子节点是否和右子节点的左子节点相同重复上述操作直到为空
代码
// 判断给定的二叉树是否对称的方法
public boolean isSymmetric(TreeNode root) {// 调用 compare 方法比较根节点的左右子树是否对称return compare(root.left, root.right);
}// 递归比较两棵树是否对称的方法
public boolean compare(TreeNode left, TreeNode right) {// 边界情况处理// 左子树不为空而右子树为空或者左子树为空而右子树不为空二叉树不对称返回 falseif (left ! null right null)return false;if (left null right ! null)return false;// 左右子树都为空认为对称返回 trueif (left null right null)return true;// 比较当前节点值是否相等若不相等二叉树不对称返回 falseif (left.val ! right.val)return false;// 递归比较左子树的左节点与右子树的右节点外侧比较boolean Outcompare compare(left.left, right.right);// 递归比较左子树的右节点与右子树的左节点内侧比较boolean Intcompare compare(left.right, right.left);// 返回外侧比较和内侧比较的与运算结果确定整棵树是否对称return Outcompare Intcompare;
}首先处理边界情况 如果 left 不为 null 而 right 为 null或者 left 为 null 而 right 不为 null则二叉树不对称返回 false。如果 left 和 right 都为 null则认为是对称的返回 true。然后比较当前节点的值 left.val 和 right.val 是否相等如果不相等则二叉树不对称返回 false。如果当前节点值相等继续递归比较 left 的左子节点 left.left 和 right 的右子节点 right.right 是否对称外侧比较。同时递归比较 left 的右子节点 left.right 和 right 的左子节点 right.left 是否对称内侧比较。最终返回外侧比较结果 Outcompare 和内侧比较结果 Intcompare 的与运算结果即判断整棵树是否对称。
相关资料
https://www.programmercarl.com/0101.%E5%AF%B9%E7%A7%B0%E4%BA%8C%E5%8F%89%E6%A0%91.html
今天的学习就到这里了
