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

0x3f第六天递归思想

news 2026/3/26 22:37:59

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:

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

右视图：