手机怎么注册网站,手机版cad简单制图,58同城淄博网站建设,品牌关键词优化资料引用#xff1a; 226.翻转二叉树#xff08;226.翻转二叉树#xff09; 101.对称二叉树#xff08;101.对称二叉树#xff09; 104.二叉树的最大深度#xff08;104.二叉树的最大深度#xff09; 111.二叉树的最小深度#xff08;111.二叉树的最小深度#xff09;… 资料引用 226.翻转二叉树226.翻转二叉树 101.对称二叉树101.对称二叉树 104.二叉树的最大深度104.二叉树的最大深度 111.二叉树的最小深度111.二叉树的最小深度 226.翻转二叉树226.翻转二叉树
题目分析
给定一棵二叉树的根节点root翻转二叉树使每一棵子树的根节点的左右孩子交换最后返回根节点。
解题重点
选择合适的遍历方式以便于处理。
解题思路
考虑采取递归的遍历方式进行处理使用前序或后序遍历皆可。
递归函数的参数待处理的子树根节点递归函数的返回值处理完毕的子树根节点递归函数的终止条件遇到空节点直接返回递归函数的单层递归逻辑 前序遍历终止条件判断、swap左右孩子递归进入左孩子递归进入右孩子返回当前根节点后序遍历终止条件判断、递归进入左孩子递归进入右孩子swap左右孩子返回当前根节点
注意
为什么不使用中序遍历
因为中序遍历是左中右先完成对左子树的翻转再将左右子树互换此时若再对当前的右子树做翻转实际上是对互换前的、已经完成翻转的“前左子树”做翻转。
修改方式左中“左”
总结反思
需要把握好不同遍历方式下处理操作的顺序尤其是前后序和中序之间的区别。
class Solution {public TreeNode invertTree(TreeNode root) {if (root null) return root;swap_Kids(root);invertTree(root.left);invertTree(root.right);return root;}public void swap_Kids (TreeNode root) {TreeNode tmpNode root.left;root.left root.right;root.right tmpNode;return;}
}
101.对称二叉树101.对称二叉树
题目分析
给定一个二叉树的根节点root判断其是否为轴对称的即翻转后树的节点值是否不变包括空值。
解题重点
选择合适的遍历方式方便比较。
简单思路
先遍历取节点值包括空值用StringBuilder存储便于存储空值
再翻转二叉树
最后用相同的方式遍历取节点值实时比较是否与第一步得到的字符数组相同。
此处采取前序遍历。
class Solution {public boolean isSymmetric(TreeNode root) {if (root null) return true;StringBuilder sb1 new StringBuilder();StringBuilder sb2 new StringBuilder();preOrder(root, sb1);invertTree(root);preOrder(root, sb2);return sb1.toString().equals(sb2.toString());}public void preOrder(TreeNode root, StringBuilder sb){if(root null) {sb.append(\0);return;}sb.append(Integer.toString(root.val));preOrder(root.left, sb);preOrder(root.right, sb);}public TreeNode invertTree(TreeNode root) {if (root null) return root;swap_Kids(root);invertTree(root.left);invertTree(root.right);return root;}public void swap_Kids (TreeNode root) {TreeNode tmpNode root.left;root.left root.right;root.right tmpNode;return;}
}
推荐思路
比较的不是二叉树的左右节点比较的是根节点的左子树和右子树是不是相互翻转的即比较对象是左右子树。
因此在递归遍历过程中要同时遍历两棵树。
由翻转的特性我们定义靠近中轴的是里侧节点远离中轴的外侧节点。
选择“后序遍历”通过递归函数的返回值判断两个子树之间的内侧节点和外侧节点是否相等。
准确来说对两个子树的遍历应当分别为左右中和右左中。
定义递归比较函数compare如下 递归函数的参数左右子树节点递归函数的返回值布尔值确定终止条件 节点为空的情况 左空右非空return false左非空右空return false左右都为空对称return true 节点非空的情况 左右都非空节点值不同false相同继续 递归函数的单层递归逻辑处理 左右节点都不为空且数值相同的情况 递归比较左孩子的左孩子 和 右孩子的右孩子外侧节点递归比较左孩子的右孩子 和 右孩子的左孩子里侧节点取前两者的逻辑并返回该值。
class Solution {public boolean isSymmetric(TreeNode root) {if (root null) return true;return compareLR(root.left, root.right);}public boolean compareLR(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 if (left.val ! right.val) return false;// 递归比较外侧节点和里侧节点取逻辑并boolean outside compareLR(left.left, right.right);boolean inside compareLR(left.right, right.left);boolean isSame outside inside;return isSame;}
}
总结反思
学会根据任务需求灵活调整遍历方式进行比较。
递归中的三要素需要在掌握的基础上根据实际情况来调整完善尤其是终止条件的合理设定非常重要。
104.二叉树的最大深度104.二叉树的最大深度
题目分析
给定一个二叉树返回其最大深度。
解题重点
对于一个二叉树求其最大深度则在递归遍历过程中增加deep参数的传递。
注意
最大深度定义为从根节点到最远叶子节点的最长路径上的节点数因此最小深度从1开始根节点不为空若为空返回0。
解题思路
构造递归函数getMaxDepth如下
递归函数的参数节点node当前深度deep递归函数的返回值最终深度deep整型递归函数的终止条件遇到空节点返回当前deep递归函数的单层递归逻辑节点为空返回deep。节点不为空deep递归查询左子树的最大深度left_depth和右子树的最大深度right_depth取较大者返回。
总结
注意通过递归函数的参数传递实现当前深度deep的记录并注意比较左右子树取较大者。
class Solution {public int maxDepth(TreeNode root) {return getMaxDepth(root, 0);}public int getMaxDepth(TreeNode root, int deep) {if (root null) return deep;deep;int left_depth getMaxDepth(root.left, deep);int right_depth getMaxDepth(root.right, deep);return left_depth right_depth ? left_depth : right_depth;}
}
111.二叉树的最小深度111.二叉树的最小深度
题目分析
给定一个二叉树的根节点root找出其最小深度。
注意
最小深度的定义从根节点到最近叶子结点的最短路径上的节点数。
解题重点
需要排除左右子树为空的这条路径
解题思路与优化
后序遍历
自底向上求高度等价于求深度终止条件是遇到空节点时返回0叶子节点为从1开始通过递归的逐级返回进行自增即可注意排除节点为空的情况不可作为最小深度比较对象
前序遍历
自顶向下求深度终止条件是遇到空节点时不自增直接返回当前积累深度deep通过递归返回的是最底层的计算结果是通过逐级向下递归时自增的需要额外增加参数--当前深度deep因此需要构造新的递归函数相较后序并不简洁但也可实现。
层序遍历迭代法
层序遍历通过队列实现需要注意的是只有当左右孩子都为空才说明是抵达叶子节点否则继续首次抵达叶子结点时由于层序遍历是从上往下遍历所以正是最近叶子节点
总结反思
理解前序遍历和后序遍历的“方向”区别根据实际情景选取适合的遍历方式。
理解题意很重要不要经验主义下判断~
/*后序遍历 递归法*/
class Solution {/*该解法实际是后序遍历相当于求最小高度等价于求最小深度 */public int minDepth(TreeNode root) {if (root null) return 0;int leftDepth minDepth(root.left);int rightDepth minDepth(root.right);if (root.left null) return rightDepth1;if (root.right null) return leftDepth1;return leftDepth rightDepth ? leftDepth1 : rightDepth1;}
}
/*前序遍历 递归法*/
class Solution {public int minDepth(TreeNode root) {return getMinDepth(root, 0);}public int getMinDepth(TreeNode root, int deep) {if (root null) return deep;deep;int left_depth 0;int right_depth 0;if (root.left null) return getMinDepth(root.right, deep);else if (root.right null) return getMinDepth(root.left, deep);left_depth getMinDepth(root.left, deep);right_depth getMinDepth(root.right, deep);return left_depth right_depth ? left_depth : right_depth;}
}
/*层序遍历 迭代法*/
class Solution {public int minDepth(TreeNode root) {if (root null) {return 0;}DequeTreeNode deque new ArrayDeque();deque.offer(root);int depth 0;while (!deque.isEmpty()) {int size deque.size();depth;for (int i 0; i size; i) {TreeNode poll deque.poll();if (poll.left null poll.right null) {// 因为从上往下遍历所以是最近叶子结点该值就是最小值直接返回depthreturn depth;}if (poll.left ! null) {deque.offer(poll.left);}if (poll.right ! null) {deque.offer(poll.right);}}}return depth;}
}
