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

小程序网站开发公司大数据查询平台

news 2026/4/6 5:46:43

小程序网站开发公司,大数据查询平台,centos wordpress 整站,咨询公司英文资料引用： 226.翻转二叉树（226.翻转二叉树） 101.对称二叉树（101.对称二叉树） 104.二叉树的最大深度（104.二叉树的最大深度） 111.二叉树的最小深度（111.二叉树的最小深度）…

资料引用：

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;}
}

总结反思：

学会根据任务需求灵活调整遍历方式进行比较。

递归中的三要素需要在掌握的基础上根据实际情况来调整完善，尤其是终止条件的合理设定，非常重要。

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 rightDepth+1;if (root.right == null) return leftDepth+1;return leftDepth < rightDepth ? leftDepth+1 : rightDepth+1;}
}
/*前序遍历 递归法*/
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;}Deque<TreeNode> 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;}
}

查看全文

http://www.hkea.cn/news/124319/