🌲 深入理解二叉树结构变化与路径特性（力扣104 / 226 / 114 / 543）
在解题过程中，我们不仅要掌握二叉树的遍历方法，还需要理解它的结构特性。本篇博客将围绕二叉树的 深度计算、结构变换与路径分析 展开，涉及以下四道高频题：
- [x] 104. 二叉树的最大深度
- [x] 226. 翻转二叉树
- [x] 114. 二叉树展开为链表
- [x] 543. 二叉树的直径
📌 104. 二叉树的最大深度
✅ 题目描述：
给定一棵二叉树，找出其最大深度。最大深度是从根节点到最远叶子节点的最长路径上的节点数。
💡 解题思路：
这是一道非常经典的递归题。最大深度 = 左子树最大深度 与 右子树最大深度中的较大者 + 1。
我们可以使用 后序遍历（DFS），从叶子节点向上递归：
🧠 步骤解析：
- 递归终止条件：节点为空，返回0。
- 分别递归计算左右子树的最大深度。
- 当前节点的最大深度 = max(左，右) + 1。
💻 Go 实现：
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
left := maxDepth(root.Left)
right := maxDepth(root.Right)
return max(left, right) + 1
}
📌 226. 翻转二叉树
✅ 题目描述：
翻转一棵二叉树，即左右子树交换。
示例：
输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1
💡 解题思路：
本质是递归地交换左右子树，可以用前序遍历来交换每个节点的左右子树。
🧠 步骤解析：
- 如果当前节点为 nil，返回 nil。
- 递归翻转左右子树。
- 交换左右子树。
💻 Go 实现：
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}
root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
📌 114. 二叉树展开为链表
✅ 题目描述：
将二叉树原地展开为一个单链表，使用前序遍历顺序，即所有右指针指向下一个节点，左指针置空。
💡 解题思路：
需要在原地修改树结构，我们可以借助 后序遍历 反向处理。
- 倒着处理每个节点，将右子树先展开，再左子树展开，然后将当前节点的右指针指向上一个访问节点（类似于链表的前插操作）。
🧠 步骤解析（后序遍历 + 记录上一个节点）：
- 先递归右子树，再递归左子树。
- 每次处理当前节点时，将其右指针指向前一个访问的节点（pre），左指针置空。
- 更新 pre 为当前节点。
💻 Go 实现：
var prev *TreeNode
func flatten(root *TreeNode) {
if root == nil {
return
}
flatten(root.Right)
flatten(root.Left)
root.Right = prev
root.Left = nil
prev = root
}
📌 543. 二叉树的直径
✅ 题目描述：
给定一棵二叉树，计算它的直径。直径是任意两个节点之间的最长路径，路径长度是节点数之差。
💡 解题思路：
路径可能穿过某个节点的左右子树，因此我们可以在计算深度时顺便计算当前节点左右深度之和，并维护最大值。
🧠 步骤解析（递归 + 回溯）：
- 定义一个全局变量
res，记录最长路径。 - 在递归函数中，分别计算左右子树深度。
- 更新
res = max(res, left + right)。 - 每次返回左右子树中最大深度 + 1。
💻 Go 实现：
var res int
func diameterOfBinaryTree(root *TreeNode) int {
res = 0
dfs(root)
return res
}
func dfs(root *TreeNode) int {
if root == nil {
return 0
}
left := dfs(root.Left)
right := dfs(root.Right)
res = max(res, left+right)
return max(left, right) + 1
}
🧠 小结与思考
| 题号 | 关键词 | 思维方法 | 特点 |
|---|---|---|---|
| 104 | 最大深度 | 后序遍历 | 求树高的典型题目 |
| 226 | 翻转结构 | 前序递归 | 每层交换左右子树 |
| 114 | 展开链表 | 后序遍历 | 倒序拼接前序路径 |
| 543 | 最大路径 | 递归+回溯 | 求路径最大值 |
📌 总结
- 熟练掌握递归遍历策略（前序、中序、后序），在结构变化题中尤为重要。
- 遇到路径相关问题时，可结合深度计算与回溯策略。
- 在链表化或结构修改题目中，注意是否需要原地修改、是否可以使用辅助变量。
✍️ 下一篇我们将讨论“二叉树的构造”相关问题（105 & 108），包括如何根据前序中序构造树，以及如何构造平衡 BST。敬请期待！
如果这篇文章对你有帮助，欢迎点赞 👍、收藏 ⭐、关注 💻！持续更新 LeetCode 高频题详解 🚀🌲
