day14 代码随想录算法训练营 二叉树专题2

1 今日打卡题

翻转二叉树 226. 翻转二叉树 – 力扣（LeetCode）

对称二叉树 101. 对称二叉树 – 力扣（LeetCode）

二叉树的最大深度 104. 二叉树的最大深度 – 力扣（LeetCode）

二叉树的最小深度 111. 二叉树的最小深度 – 力扣（LeetCode）

2 翻转二叉树

2.1 思路

翻转二叉树的本质是：把二叉树中每个节点的左子节点和右子节点交换位置，并且这个操作需要递归地应用到所有节点上（包括子树的节点）。递归的核心逻辑可以拆解为 3 步： 终止条件：如果当前节点为 null（空节点），直接返回，无需反转（递归的出口，避免无限递归）。 处理当前节点：交换当前节点的左、右子节点。 递归处理子节点：分别对当前节点的左子树、右子树执行反转操作（因为子树本身也是一棵二叉树，需要同样的逻辑反转）。

可以用前序遍历或者后序遍历。但是中序遍历不行，因为有的会翻转2次，有的遍历不到。

2.2 实现代码

class Solution {
// 主方法：反转二叉树，返回反转后的根节点
public TreeNode invertTree(TreeNode root) {
// 递归终止条件：当前节点为空，直接返回（没有可反转的节点）
if (root == null) {
return root;
}

// 第一步：处理当前节点——交换当前节点的左、右子节点
swap(root);

// 第二步：递归反转左子树（左子树也是一棵二叉树，需要同样的逻辑）
invertTree(root.left);

// 第三步：递归反转右子树（右子树也是一棵二叉树，需要同样的逻辑）
invertTree(root.right);

// 返回反转后的根节点
return root;
}

// 辅助方法：交换一个节点的左、右子节点
private void swap(TreeNode node) {
// 临时变量保存左子节点
TreeNode temp = node.left;
// 把右子节点赋值给左子节点
node.left = node.right;
// 把临时保存的左子节点赋值给右子节点
node.right = temp;
}
}

3 对称二叉树

3.1 思路

判断一棵二叉树是否对称，本质是判断二叉树的左子树和右子树是否互为镜像，镜像的核心条件是： 两个对应节点的值相等； 节点 A 的左子节点 要和 节点 B 的右子节点 对称； 节点 A 的右子节点 要和 节点 B 的左子节点 对称； 递归终止条件：要么两个节点都为空（对称），要么一个为空一个不为空（不对称），要么值不相等（不对称）。

递归的逻辑是：先判断当前层的两个节点是否对称，再递归判断内层、外层子节点是否都对称，只有所有层级都满足，才是对称二叉树。

3.2 实现代码

class Solution {
// 主方法：判断二叉树是否对称
public boolean isSymmetric(TreeNode root) {
// 特殊情况：根节点为空，直接认为是对称的
if (root == null) {
return true;
}
// 核心逻辑：比较根节点的左子树和右子树是否互为镜像
return compare(root.left, root.right);
}

// 辅助递归方法：比较两个节点（左子树节点和右子树节点）是否对称
private boolean compare(TreeNode left, TreeNode right) {
// 情况1：左节点为空，右节点不为空 → 不对称
if (left == null && right != null) {
return false;
}
// 情况2：左节点不为空，右节点为空 → 不对称
else if (left != null && right == null) {
return false;
}
// 情况3：左右节点都为空 → 对称（递归终止的有效条件）
else if (left == null && right == null) {
return true;
}
// 情况4：左右节点都不为空，但值不相等 → 不对称
else if (left.val != right.val) {
return false;
}

// 走到这里，说明当前左右节点值相等，需要递归判断「外层」和「内层」是否都对称
// 外层：左节点的左子节点 ↔ 右节点的右子节点（镜像的外侧）
boolean outside = compare(left.left, right.right);
// 内层：左节点的右子节点 ↔ 右节点的左子节点（镜像的内侧）
boolean inside = compare(left.right, right.left);

// 只有外层和内层都对称，当前两个节点才是对称的
return outside && inside;
}
}

4 二叉树的最大深度

4.1 思路

终止条件：如果当前节点为 null（空节点），深度为 0（没有节点就没有深度）； 递归分解：分别计算当前节点的左子树最大深度和右子树最大深度； 合并结果：当前节点的深度 = 左右子树深度的最大值 + 1（+1 是因为要包含当前节点本身）。

用后序遍历

4.2 实现代码

class Solution {
// 主方法：求二叉树最大深度
public int maxDepth(TreeNode root) {
// 终止条件：空节点深度为0
if (root == null) {
return 0;
}
// 递归计算左子树深度
int leftDepth = maxDepth(root.left);
// 递归计算右子树深度
int rightDepth = maxDepth(root.right);
// 当前节点深度 = 左右子树最大值 + 1（当前节点）
return Math.max(leftDepth, rightDepth) + 1;
}
}

5 二叉树的最小深度

5.1 思路

终止条件：和最大深度一致 → 如果当前节点为 null，返回 0； 特殊情况处理（最大深度没有这一步）： 如果当前节点只有左子树（右子树为空）：最小深度 = 左子树深度 + 1（因为右子树为空，无法构成到叶子的路径）； 如果当前节点只有右子树（左子树为空）：最小深度 = 右子树深度 + 1（同理）； 普通情况：当前节点既有左子树又有右子树 → 最小深度 = 左右子树深度的最小值 + 1（和最大深度的 max 改为 min）。

5.2 实现代码

class Solution {
public int minDepth(TreeNode root) {
// 终止条件：空节点的深度为0
if (root == null) {
return 0;
}

// 递归计算左子树的深度
int leftDepth = minDepth(root.left);
// 递归计算右子树的深度
int rightDepth = minDepth(root.right);

// 特殊情况1：当前节点只有左子树（右子树为空）→ 只能走左子树
if (root.left != null && root.right == null) {
return 1 + leftDepth;
}
// 特殊情况2：当前节点只有右子树（左子树为空）→ 只能走右子树
else if (root.left == null && root.right != null) {
return 1 + rightDepth;
}
// 普通情况：既有左子树又有右子树 → 取左右子树深度的最小值 + 当前层
else {
return 1 + Math.min(leftDepth, rightDepth);
}
}
}

6 额外题目

6.1 相同的树（与对称二叉树相似）100. 相同的树 – 力扣（LeetCode）

6.1.1 思路

终止条件： 两棵树的当前节点都为空 → 相同，返回 true； 一个为空、一个不为空 → 结构不同，返回 false； 都不为空但值不相等 → 值不同，返回 false。 递归逻辑： 当前节点满足条件后，递归判断p 的左子节点 和 q 的左子节点是否相同； 递归判断p 的右子节点 和 q 的右子节点是否相同； 只有左右子树都相同，整棵树才相同（返回 left && right）。

6.1.2 实现代码

class Solution {
// 主方法：判断两棵树p和q是否完全相同
public boolean isSameTree(TreeNode p, TreeNode q) {
// 情况1：p和q的当前节点都为空 → 结构匹配，返回true（递归终止条件）
if (p == null && q == null) {
return true;
}
// 情况2：p为空但q不为空 → 结构不匹配，返回false（递归终止条件）
else if (p == null && q != null) {
return false;
}
// 情况3：p不为空但q为空 → 结构不匹配，返回false（递归终止条件）
else if (p != null && q == null) {
return false;
}
// 情况4：p和q都不为空，但值不相等 → 值不匹配，返回false（递归终止条件）
else if (p.val != q.val) {
return false;
}

// 走到这里：当前节点值相等、结构也匹配，需要递归判断子节点
// 递归判断左子树：p的左子节点 ↔ q的左子节点（和对称树的核心区别！）
boolean left = isSameTree(p.left, q.left);
// 递归判断右子树：p的右子节点 ↔ q的右子节点（和对称树的核心区别！）
boolean right = isSameTree(p.right, q.right);

// 只有左右子树都相同，当前两棵树才相同
return left && right;
}
}

6.2 另一颗树的子树572. 另一棵树的子树 – 力扣（LeetCode）

6.2.1 思路

在相同的树基础上改造而来。

判断 subRoot 是 root 的子树，本质是：把 root 中的每一个节点都当作 “候选根节点”，检查以该节点为根的子树是否和 subRoot 完全相同；只要有一个候选节点匹配成功，就返回 true，否则返回 false。

外层递归（isSubtree）的完整逻辑 终止条件：如果当前 root 为空，说明已经遍历到叶子节点的子节点，没有匹配可能，返回 false； 当前节点检查：如果以当前 root 为根的子树和 subRoot 相同（调用 isSameTree 返回 true），直接返回 true； 递归遍历子树：如果当前节点不匹配，就递归检查root 的左子树和root 的右子树是否包含 subRoot，只要其中一个返回 true，整体就返回 true； 最终结果：只有所有节点都检查过且都不匹配，才返回 false。

6.2.2 实现代码  

class Solution {
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
// 终止条件：root为空，没有子树能匹配，返回false
if (root == null) {
return false;
}

// 情况1：当前root和subRoot完全相同 → 找到子树，返回true
if (isSameTree(root, subRoot)) {
return true;
}

// 情况2：当前节点不匹配，递归找「左子树的所有节点」和「右子树的所有节点」
// 关键：这里要调用 isSubtree 而不是 isSameTree！
boolean leftFind = isSubtree(root.left, subRoot); // 递归遍历左子树的所有节点
boolean rightFind = isSubtree(root.right, subRoot); // 递归遍历右子树的所有节点

// 只要左/右子树里有一个找到，就返回true
return leftFind || rightFind;
}

// 辅助方法：判断两棵树是否完全相同（逻辑没问题，复用）
private boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
else if (p != null && q == null) return false;
else if (p == null && q != null) return false;
else if (p.val != q.val) return false;

boolean left = isSameTree(p.left, q.left);
boolean right = isSameTree(p.right, q.right);
return left && right;
}
}

6.3 N叉树的最大深度

6.3.1 思路

终止条件：如果当前节点为 null（空节点），深度为 0（和二叉树一致）； 递归逻辑： 初始化一个变量 curDepth 记录所有子节点的最大深度（初始为 0）； 遍历当前节点的所有子节点，递归计算每个子节点的深度，并用 Math.max 保留最大的那个； 合并结果：当前节点的深度 = 所有子节点的最大深度 + 1（+1 是算上当前节点本身，和二叉树一致）。 简单类比：二叉树是 “问左、右两个孩子谁的深度深”，N 叉树是 “问所有孩子谁的深度深”，最后加自己这一层。

6.3.2 实现代码

class Solution {
// 主方法：求N叉树的最大深度
public int maxDepth(Node root) {
// 递归终止条件：空节点的深度为0（和二叉树完全一致）
if (root == null) {
return 0;
}

// 初始化当前节点所有子节点的最大深度为0
int curDepth = 0;

// 遍历当前节点的所有子节点（核心区别：二叉树只遍历left/right，N叉树遍历所有children）
for (int i = 0; i < root.children.size(); i++) {
// 递归计算当前子节点的深度，并用Math.max保留最大的子节点深度
curDepth = Math.max(maxDepth(root.children.get(i)), curDepth);
}

// 当前节点的深度 = 所有子节点的最大深度 + 1（当前节点本身）
return curDepth + 1;
}
}