0x3f第六天 递归思想

1.递归思想：

首先弄清楚递和归

递就是将一个大问题分解为多个相同的子问题

在计算机真正实现的时候，计算机会一个个将你递的问题，放进栈中，这也是为什么递归 的时候空间复杂度是O（n），计算机背后实际上创建了一个深度为n 的栈，当前在处理那一层，栈都有对应

把一个复杂的大问题，按照相同的逻辑拆解成规模更小的子问题，直到子问题小到能直接解决（触达边界条件）。

比如 if root == None： 就是已经递到最底下了，完成全部的递了

• 核心作用：避免递归无限拆解（栈溢出），同时为 “归” 提供初始结果。

现在开始规，而归就是执行非边界条件，做逻辑

计算机行为：栈是 “先进后出” 的，最后压入的子问题先出栈计算，结果向上传递给上一层问题。

class Solution: def maxDepth(self, root: TreeNode) -> int: # 边界条件：递的终止 if root is None: return 0 # 递：触发子问题，等待子问题的归结果 left_depth = self.maxDepth(root.left) right_depth = self.maxDepth(root.right) # 归：显性拆分两步，更易理解 # 第一步：合并子问题结果（找左右子树的最大深度） max_child_depth = max(left_depth, right_depth) # 第二步：计算当前层深度（子树最大深度 + 当前节点），返回（向上归） current_depth = max_child_depth + 1 return current_depth

还有前序遍历的思路：

# class Solution: # def maxDepth(self, root:Optional[TreeNode])->int : # ans = 0 # def qianxubianli(node,cnt): # if root == None: # return 0 # nonlocal ans # cnt += 1 # ans = max(ans, cnt) # qianxubianli(root.left,cnt) # qianxubianli(root.right,cnt) # qianxubianli(root,0) # return ans

---

---

2.相同的树：

递归检查子树：分别递归判断p和q的左子树、右子树是否相同，把结果存在两个变量里。

a = self.isSameTree(p.left,q.left)

b = self.isSameTree(p.right,q.right)

return a and b

在此基础上加上边界条件：if p ==None or q == None

class Solution: def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: #首先核心如何比较两个树，就是比较两个树的左子树，比较两个数的右子树 if p ==None or q == None: #情况一：p或q只是有一个空节点 return p == q # if p.val != q.val: #情况二：pq不空，但不相等，剪枝操作，没必要后续再递归 # return False a = self.isSameTree(p.left, q.left) b = self.isSameTree(p.right, q.right) return a and b and p.val == q.val

---

---

---

3.对称树

思路核心：虽然紧接着上个题，很容易想到构造一个isSameTree

但还是要总结一下

拆分成子问题，就是比较两个树的节点，比较A树的左节点和B树的右节点是否一样

但题目只给了root一个根节点，那就把它拆开

然后就有了整体的思路了

class Solution: def isSymmetric(self, root: Optional[TreeNode]) -> bool: def isSameTree(node1,node2): if node1 == None or node2== None: return node1 == node2 a = isSameTree(node1.left,node2.right) b = isSameTree(node1.right,node2.left) return a and b and node1.val==node2.val return isSameTree(root.left,root.right)

还可以进一步优化：

两个空树也是对称树

所以加上

if root is None

核心价值：优先处理空树，本质是「鲁棒性保障」（避免崩溃）

• 用例 1：root = []（空树）；
• 用例 2：root = [1]（单节点树，左 / 右子树都是空）；
• 用例 3：root = [1,2,2]（非空树，但子节点包含空）。

如果没处理root=None，用例 1 直接报错，用例 2 也要走递归处理 “两个空节点”，执行耗时自然被拉高。

相同树的核心是「对比两棵独立的树」（入口直接传两棵树的根节点），对称树的核心是「把一棵树拆成左右两半，对比这两半是否镜像」（入口只传一棵树的根节点，必须先拆成 left/right 再对比）。

这也就是为何对称树要额外加一个判断初始给的root是否为空咯

---

---

---

4.平衡树：

子问题不是比较左右子树的高度吗，那不是应该分开求左右子树高度：

你的理解有个关键偏差：“判断平衡” 的子问题不是 “先分开求完左右高度再比较”，而是 “在求高度的过程中同步判断平衡” ——后者（自底向上）比前者（自顶向下分开求）效率高一个量级，而 max(left_height, right_height) + 1 正是 “求高度 + 判平衡” 的核心衔接点

-1是 “带不平衡标记的数值”

要理解为什么求树高 + 判平衡的递归函数用get_height(node)而非get_height(node, depth)，核心是：这个函数的核心目标是「自底向上计算节点高度」，高度由子树推导而来，而非依赖外部传入的「depth（深度）」；而 depth 是「自顶向下标记层级」的变量，和 “高度计算” 的逻辑无关。

def get_height(node): if not node: return 0 # 求左高度的同时，若左子树不平衡直接返回-1（剪枝） left_h = get_height(node.left) if left_h == -1: return -1 # 求右高度的同时，若右子树不平衡直接返回-1（剪枝） right_h = get_height(node.right) if right_h == -1: return -1 # 求完左右高度后，立刻判当前节点的平衡 if abs(left_h - right_h) > 1: return -1 # 平衡则返回当前节点高度（供父节点判断） else: return max(left_h, right_h) + 1

流程：递归左+判断子节点是否传上来了-1

递归右+判断子节点是否传上来了-1

子节点为什么会传上来-1： if abs(left_h - right_h) > 1:

返回节点高度：这一步和求树高度是一样的一句话

---

---

右视图：

一、先明确递归的核心逻辑（你提到的关键结论）

递归解决树的问题的本质：

1. 边界条件：定义 “递归什么时候停”（通常是空节点）；
2. 最小问题：只关注 “当前节点该做什么”，不用管子树的细节；
3. 子树等价性：假设递归调用能正确处理 “左 / 右子树”（返回子树的有效结果），只需基于子树结果处理当前节点即可。

1. 边界条件：定义递归的终止规则（最小的 “无意义问题”）

• 边界条件的意义：空节点是递归中 “最小的无效问题”—— 空节点没有值，也没有子树，无需处理，直接返回即可；
• 这是递归的 “底线”，保证递归不会无限执行，也避免了对 “无意义节点” 的无效计算。

2. 最小问题：只关注 “当前节点该做什么”（不用管子树）

• 最小问题的定义：对于任意一个非空节点，它只需要判断 “自己是否是当前层的第一个被访问节点”—— 这是当前节点的 “唯一职责”，不用管左 / 右子树长什么样、怎么遍历；

3. 子树等价性：假设递归能处理子树，只需复用其逻辑

---

我们还原右视图的完整解题思考过程，就能更清晰看到 “先第三步、后第二步” 的逻辑：

1. 问题目标：找每一层的最右侧节点；
2. 核心难点：如何保证 “先访问最右侧节点”？→ 想到 “右优先 DFS”（第三步的思路）；
3. 衍生问题：如何标记 “每一层第一个被访问的节点”？→ 想到 “depth 和 len (ans) 匹配”（第二步的思路）；
4. 代码落地：把思路转化为 “先判断标记（第二步）、再递归遍历（第三步）”（符合递归自顶向下的执行逻辑）。