LeetCode 100/101/110/199 对称/平衡二叉树与右视图

目录

一、100. 相同的树

问题描述

核心思想：递归分治

实现方法

重点 & 难点

二、101. 对称二叉树：“镜像问题”

问题描述

核心思想

实现方法

方法 1：递归（辅助函数比较两棵子树）

方法 2：迭代（队列成对存储镜像节点）

重点 & 难点

三、110. 平衡二叉树：后序遍历的 “剪枝”

问题描述

核心思想

实现方法（优化版：后序遍历 + 剪枝）

重点 & 难点

四、199. 二叉树的右视图：遍历顺序的 “状态控制”

问题描述

核心思想：层序遍历 / 优先右子树的 DFS

实现方法

方法 1：层序遍历（直观易理解）

方法 2：DFS（优先右子树）

重点 & 难点

总结：二叉树问题的通用解题逻辑

1. 递归分治：拆解子问题

2. 遍历控制：记录状态

模板使用总结

本文会拆解 LeetCode 中 4 道二叉树高频题 ——100. 相同的树、101. 对称二叉树、110. 平衡二叉树、199. 二叉树的右视图，从核心思想、实现方法到重点难点做深入分析。

一、100. 相同的树

问题描述

给定两棵二叉树的根节点p和q，判断二者是否结构相同且对应节点值相等。

核心思想：递归分治

树的递归结构决定了 “整棵树相同” 可以拆解为 3 个子问题：

1. 当前节点的值相等；
2. p的左子树与q的左子树相同；
3. p的右子树与q的右子树相同。

实现方法

递归的关键是处理边界条件（空节点是二叉树递归的 “必考题”）：

碰到递归问题，先从边界条件出发，慢慢推导

class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { // 边界1：两棵树都空，相同 if (p == null && q == null) return true; // 边界2：其中一棵空、另一棵非空，不同 if (p == null || q == null) return false; // 子问题：值相等 + 左子树相同 + 右子树相同 return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right); } }

重点 & 难点

• 重点：递归的 “分治拆解”—— 把整树问题拆成 “当前节点 + 左右子树” 的子问题；
• 难点：容易忽略 “一个空、一个非空” 的边界条件，导致空指针异常或逻辑错误。

二、101. 对称二叉树：“镜像问题”

问题描述

给定一棵二叉树的根节点root，判断其是否是镜像对称的（即左右子树呈镜像结构）。

核心思想：转化为 “两棵树的镜像比较”

“一棵树对称” 等价于 “它的左子树和右子树互为镜像”，而 “两棵树镜像” 的子问题是：

1. 树 A 的根节点值 = 树 B 的根节点值；
2. 树 A 的左子树 与 树 B 的右子树 镜像；
3. 树 A 的右子树 与 树 B 的左子树 镜像。

实现方法

方法 1：递归（辅助函数比较两棵子树）

class Solution { public boolean isSymmetric(TreeNode root) { // 空树是对称的；否则比较左、右子树是否镜像 return root == null ? true : isMirror(root.left, root.right); } // 辅助函数：判断两棵树是否镜像 private boolean isMirror(TreeNode a, TreeNode b) { if (a == null && b == null) return true; if (a == null || b == null) return false; // 子问题：值相等 + 左对右、右对左 return a.val == b.val && isMirror(a.left, b.right) && isMirror(a.right, b.left); } }

方法 2：迭代（队列成对存储镜像节点）

用队列将 “需要比较的镜像节点” 成对入队，每次取出一对节点校验：

public boolean isSymmetric(TreeNode root) { if (root == null) return true; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root.left); queue.offer(root.right); while (!queue.isEmpty()) { TreeNode a = queue.poll(); TreeNode b = queue.poll(); // 处理空节点的情况 if (a == null && b == null) continue; if (a == null || b == null) return false; if (a.val != b.val) return false; // 成对入队镜像节点：a左对b右，a右对b左 queue.offer(a.left); queue.offer(b.right); queue.offer(a.right); queue.offer(b.left); } return true; }

重点 & 难点

• 重点：问题转化 —— 将 “一棵树的对称” 转化为 “两棵子树的镜像比较”，是递归的关键；
• 难点：镜像节点的对应关系（左对右、右对左）容易搞反，导致逻辑错误。

三、110. 平衡二叉树：后序遍历的 “剪枝”

问题描述

判断一棵二叉树是否是平衡二叉树（AVL 树）：每个节点的左右子树高度差的绝对值不超过 1。

核心思想：后序遍历 + 剪枝

平衡二叉树需要先获取子树高度，再判断当前节点的平衡度—— 后序遍历（左→右→根）恰好符合 “先处理子树、再处理根” 的需求。

同时，为了避免重复计算子树高度（基础版会重复计算），我们可以在计算高度的同时集成平衡判断：若某子树不平衡，直接返回标记值（如-1），提前终止递归（剪枝）。

实现方法（优化版：后序遍历 + 剪枝）

class Solution { public boolean isBalanced(TreeNode root) { // 若返回-1则不平衡，否则平衡 return getHeightAndCheck(root) != -1; } // 辅助函数：计算高度 + 检查平衡，不平衡返回-1 private int getHeightAndCheck(TreeNode node) { if (node == null) return 0; // 空节点高度为0 // 先检查左子树 int leftHeight = getHeightAndCheck(node.left); if (leftHeight == -1) return -1; // 再检查右子树 int rightHeight = getHeightAndCheck(node.right); if (rightHeight == -1) return -1; // 检查当前节点的平衡因子 if (Math.abs(leftHeight - rightHeight) > 1) return -1; // 平衡则返回当前节点高度 return Math.max(leftHeight, rightHeight) + 1; } }

重点 & 难点

• 重点：后序遍历的应用场景（需要子树信息的问题）、剪枝技巧（避免无效计算）；
• 难点：将 “高度计算” 与 “平衡判断” 合并，需要清晰的递归返回值逻辑（高度 / 不平衡标记）。

四、199. 二叉树的右视图：遍历顺序的 “状态控制”

问题描述

从二叉树的右侧观察，返回从顶部到底部能看到的节点值（即每一层的最后一个节点）。

核心思想：层序遍历 / 优先右子树的 DFS

• 层序遍历（BFS）：记录每一层的节点数，遍历完一层后，取最后一个节点；
• 深度优先遍历（DFS）：优先访问右子树，记录当前深度，当深度等于结果列表长度时，说明是该层的 “第一个可见节点”（因先右，所以是最右侧）。

实现方法

方法 1：层序遍历（直观易理解）

class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); // 当前层的节点数 for (int i = 0; i < levelSize; i++) { TreeNode node = queue.poll(); // 若为当前层最后一个节点，加入结果 if (i == levelSize - 1) { result.add(node.val); } // 左、右子节点入队（保证下一层的顺序） if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } } return result; } }

方法 2：DFS（优先右子树）

class Solution { public List<Integer> rightSideView(TreeNode root) { List<Integer> result = new ArrayList<>(); dfs(root, 0, result); return result; } private void dfs(TreeNode node, int depth, List<Integer> result) { if (node == null) return; // 深度 == 结果长度 → 该层第一个节点（先右，故为最右侧） if (depth == result.size()) { result.add(node.val); } // 优先访问右子树，深度+1 dfs(node.right, depth + 1, result); dfs(node.left, depth + 1, result); } }

重点 & 难点

• 重点：通过 “层大小”（BFS）或 “深度”（DFS）控制 “每一层的可见节点”；
• 难点：DFS 中 “深度与结果列表长度的对应关系”—— 需要理解 “先右子树” 带来的层节点顺序。

总结：二叉树问题的通用解题逻辑

这 4 道题覆盖了二叉树的核心解题思路，总结为 2 个关键词：

1. 递归分治：拆解子问题

二叉树的递归问题，核心是找到 “整树→子树” 的拆解逻辑，同时必须处理空节点的边界条件：

• 相同的树：整树相同 → 节点值 + 左子树 + 右子树相同；
• 对称二叉树：整树对称 → 左子树与右子树镜像。

2. 遍历控制：记录状态

需要按顺序访问节点或记录层 / 深度信息时，用遍历（BFS/DFS）+ 状态变量（层大小、深度）：

• 平衡二叉树：后序遍历（先子树后根）+ 高度状态；
• 右视图：层序遍历（层大小）/ DFS（深度）+ 可见节点状态。

模板使用总结

快速选型技巧

1. 看到 “平衡、相同、对称、最大深度”→ 用递归分治模板；
2. 看到 “按层、右视图、左下角、层最大值”→ 用BFS 模板；
3. 看到 “前 / 中 / 后序遍历、路径、深度优先”→ 用DFS 模板。

   ---