企业官网建设流程全解析

刷 LeetCode 二叉树专题的人，迟早都会撞上同一个困惑：递归函数里到底该返回什么？什么时候返回值，什么时候传参数？我见过太多同学卡在这道坎上——题解看懂了，代码一写就报AttributeError，或者跑出来的结果完全对不上。这一讲处理的第6题（计算布尔二叉树的值）和第7题（求根节点到叶节点数字之和），恰好把深搜的两种典型信息流向讲得明明白白：一个要求你先算清楚左右子树再回头算自己，一个要求你带着已经拼好的数字一路推进到叶子。把这两道题放在一起对比着刷，比单独背十道题模板都管用。如果你也经常在递归里绕晕，这篇文章就是按"先懂方向、再写代码"的思路来拆的。

1. 两道题为什么适合放在一起刷：深搜的两种信息流向

1.1 自顶向下与自底向上：一条分水岭

二叉树深搜的递归，本质上只有两种信息流动方向。

自顶向下，对应前序遍历的思维：递归调用时把"从根到当前节点已经累积的信息"作为参数，一路传递下去，到某个节点（通常是叶子）收获结果。生活里类比发传单——每层拿到上级给的编号，加上自己的信息继续往下传，到底之后再统一结算。第7题就是典型，走到哪个节点，手里就得握着"当前拼出的数字"。

自底向上，对应后序遍历的思维：递归先处理左右子树，拿到左右孩子的返回值后，再结合当前节点合并出本层的结果，最终由根节点汇总。生活里类比层层汇报——最底层的小兵算出自己的值报上去，组长汇总后再往上报，最后老大拿到全局结果。第6题就是典型，你不把左右子树的结果取回来，当前节点的 AND/OR 根本没法算。

很多同学分不清这两种方向，根源在于拿到题就直接写递归，没有先想清楚"数据是往上汇聚还是往下传递"。二叉树的递归其实是"方向决定形式"：数据从下往上汇，递归就返回值；数据从上往下灌，递归就加参数。这一条判断在刷遍二叉树题之前必须刻在脑子里。

1.2 第6题是"归并型"，第7题是"传递型"

第6题，计算布尔二叉树的值。给你一棵完整二叉树，叶子节点值是 0（False）或 1（True），非叶子节点值是 2（OR）或 3（AND），要你返回整棵树的布尔结果。注意这里的计算逻辑：当前节点的值一旦是 2 或 3，就代表一种运算，而运算的对象是左右子树各自的结果。也就是说，当前节点的结果完全依赖左右子树的结果，孩子不先算出来，父亲什么都干不了。这是天然的归并结构。

第7题，求根节点到叶节点数字之和。每个节点是 0~9 的数字，从根到叶子的路径拼成一个数，比如 1->2->3 就是数字 123，要求把所有路径数字加起来。跟第6题正好相反：当你站在某个节点时，从根走到这里的"前缀数字"已经确定了，接下来要继续往下走，只需要把这个前缀传给左右孩子，让孩子在此基础上扩展。每一级都在消费父级传下来的状态，这是典型的传递结构。

所以这两题放在一起是刻意为之的组合：一个让你练"怎么从子树收结果"，一个让你练"怎么往子树传状态"。把这两个方向吃透，二叉树深搜的骨架就立起来了。

2. 第6题：计算布尔二叉树的值——先算孩子，再算自己

2.1 把题意拆成一段递归逻辑

原题给的定义是"完整二叉树"（每个节点要么是叶子，要么有两个孩子），叶子 val 为 0 或 1，非叶子 val 为 2（OR）或 3（AND）。举例来说，假设一棵树长这样：

3(AND) / \ 2(OR) 1(True) / \ 0 1

手动算一遍：左子树是0 OR 1 = 1，右子树是叶子1，根节点是1 AND 1 = 1，整棵树结果是 1。这个过程已经完整演示了递归逻辑：先算左子树，再算右子树，最后回到根做合并。说白了，这就是把一条布尔表达式写成树形结构，节点就是运算符，叶子就是操作数。

读题时容易忽略的一点是：节点值 2 和 3 本身不代表真假，只代表"OR"和"AND"这两个操作。所以递归函数拿到一个非叶子节点时，不能直接拿 val 判断真假，而要先看 val 是 2 还是 3，决定用哪种逻辑运算合并左右子树的结果。我见过有同学写成return root.val == 1一路套到非叶子节点上，结果全错，就是没区分开"叶子存真值、非叶子存操作"这两层含义。

2.2 递归三要素的具体落法

老生常谈的递归三要素，在本题里可以落得很具体。

终止条件：当前节点是叶子，也就是没有孩子。叶子节点只有 0 和 1 两种值，直接返回val == 1即可。这里有个前提是完整二叉树，所以判断root.left is None就等于判断"我是叶子"，因为完整二叉树不会出现"只有右孩子没有左孩子"的情况。如果不保证完整二叉树，稳妥写法是root.left is None and root.right is None。

单层逻辑：拿到左右子树的结果 left 和 right 后，看当前节点的 val。val 为 2，执行left or right；val 为 3，执行left and right。就这两句，没有别的分支。

返回值：当前节点这棵子树的布尔结果。这个结果会被父节点继续拿去参与 AND/OR 运算。递归之所以能成立，就是因为"我相信这个函数能算对任意一棵子树"，于是只需要把当前层和子问题的关系写好，整体就自动正确。很多人喜欢在脑内展开完整递归栈，那完全是自找苦吃；你只需要盯住"当前节点拿到左右孩子的返回值后做什么"这一件事。

2.3 完整代码与短路优化

Python 实现非常短：

def evaluateTree(root): if root.left is None: # 完整二叉树：左空即叶子 return root.val == 1 # 1 -> True，0 -> False left = evaluateTree(root.left) right = evaluateTree(root.right) if root.val == 2: # OR return left or right return left and right # AND

left和right都是布尔值，所以left or right的结果也是布尔值，类型上是干净的。这里正好引出一个 Python 特有的坑：0 or 2返回 2，1 and 2返回 2，也就是 and/or 返回的是操作数本身，不保证是 bool。如果你让递归返回 int 0/1，最后return left and right可能返回一个 int，和题意要求的布尔结果不一致。解决方案就是像上面这样，叶子直接返回bool，让整个链路的类型统一。

还有个小优化空间：利用逻辑运算的短路特性。OR 时如果左子树已经为 True，右子树不需要再算；AND 时如果左子树为 False，右子树也不用再算。改写成下面的形式：

def evaluateTree(root): if root.left is None: return root.val == 1 if root.val == 2: return True if evaluateTree(root.left) else evaluateTree(root.right) return False if not evaluateTree(root.left) else evaluateTree(root.right)

对普通规模的数据，短路优化收益不大，但它符合"理解运算本质"的训练目的。面试时如果能提一句"OR/AND 存在短路剪枝"，会显得对递归理解更深入。

2.4 三个容易翻车的地方

第一个翻车点是最常见的："终止条件"只写if root is None: return False。粗看没问题，细想就炸了——叶子节点本身没有孩子，你如果只在空节点停，那访问到叶子后还会继续往root.left和root.right递归，下一层传进去的就是 None，然后你就在 None 上访问.left，直接AttributeError。正确思路是：递归要停在"叶子"而不是"空节点"，除非你愿意在递归开头统一处理 None。本题因为是完整二叉树，判断叶子只需看左孩子是否为空，简单又安全。

第二个翻车点是 Python 的 and/or 返回操作数问题，上面说过了。很多题解为了省事返回 int，然后return left or right，试几个样例好像没问题，一旦左右值变成 0 和 2 这种组合，返回类型和真值判断就乱套。建议从一开始就统一用 bool。

第三个翻车点其实是审题问题：把节点的 val 当成真值本身。记住，2 和 3 是操作符，不是 True/False。我见过有同学在非叶子节点上直接return root.val == 1，这等于把"OR/AND 操作"完全无视了，显然不可能对。

3. 第7题：求根节点到叶节点数字之和——状态跟着路径走

3.1 数字拼接的本质是乘以10再加

先看一个基本事实：从根到叶的数字，并不是等你走到叶子之后才拼出来的，而是每走一步就"长"一点。根节点 1，走到左孩子 2，数字变成 12，这等于1 * 10 + 2；再从 12 走到 5，变成 125，等于12 * 10 + 5。所以遍历过程中维护"当前数字"只需要做一件事：cur = cur * 10 + node.val。

这个公式的本质是位权展开。125 就是1*100 + 2*10 + 5，从高位往低位逐层确定，每下探一层，之前所有高位的权重都乘 10。你不需要等到路径完整再去数位数，边走边积累的递推公式恰好把这个展开过程压缩成了两次运算。

3.2 递归参数里为什么要多一个"累积值"

如果只看题目第一反应，可能有人会想：先找到所有路径，再把每条路径拼成数字求和。这当然能做，但效率低、代码丑。更贴合深搜思路的做法是：递归时不光传节点，还要传"到达这个节点之前已经拼出的数字"。

为什么必须传这个值？因为子节点无法自己知道父节点路过时拼到了哪里。比如根是 1，左子树里某个叶子路径是 1->9，它的前缀是 1；右子树里也有个叶子路径是 9，它的前缀也是 1。如果不把前缀传下去，孩子节点就只能自己往上看，那反而要维护回溯指针或者返回复杂结构。把状态放进参数里，让每层递归都知道"进入本层时，身前的数字是多少"，这就是深搜带状态的典型写法——信息在参数里流动，而不是在返回值里倒腾。

可以设想一下错误方向：如果试图用"自底向上"做这题，递归返回"子树范围内所有路径数字之和"，你会发现根本算不动——因为你不知道每条路径在高位长什么样，必须返回路径列表，最后把列表拼起来，复杂度直接爆炸。方向选错了，代码必然绕。

3.3 完整代码与None值的处理

直接给出核心实现：

def sumNumbers(root): def dfs(node, cur): if node is None: return 0 cur = cur * 10 + node.val if node.left is None and node.right is None: return cur return dfs(node.left, cur) + dfs(node.right, cur) return dfs(root, 0)

逐行解释一下意图。node is None返回 0，是因为空节点不构成一条合法路径，不应该贡献任何数字；0 是加法的恒等元，所以不会干扰求和。cur = cur * 10 + node.val放在叶子判断之前，是因为叶子节点自身也要参与数字拼接，不能漏掉最后一位。判断叶子必须左右孩子都为空，这是路径终点的唯一标准。到达叶子后直接返回 cur，这条路径上的数字就结算完成。非叶子则把累积值分别传给左右孩子，最终的和来自左右子树贡献之和。

一个容易写错的小细节：很多人会把node is None的判断和叶子判断的先后顺序搞反。正确的顺序是先排除 None，再判断叶子，否则对叶子继续访问左右孩子时，会拿着 None 去递归，又变成空指针。另一个细节是dfs(None, cur)一定返回 0，不能返回 cur——如果返回 cur，同一个叶子会被父节点两侧的空子节点重复计数，答案会翻倍错。

3.4 回溯写法对比：为什么要撤销选择

既然系列标题里有"回溯"，这里值得展开说说同为深搜的两种写法差异。上面是"算术状态"版本，通过不可变整数传递累积值；下面这种显式记录路径的回溯版本，在很多树的题目里也很常见：

def sumNumbers(root): ans = 0 path = [] def backtrack(node): nonlocal ans if node is None: return path.append(node.val) if node.left is None and node.right is None: num = 0 for d in path: num = num * 10 + d ans += num else: backtrack(node.left) backtrack(node.right) path.pop() backtrack(root) return ans

注意这里path.pop()为什么要放在递归返回后？因为path是一个 Python 列表，属于可变对象，所有递归层级共享同一个引用。你往左子树递归时往 path 里加了节点，如果不 pop 掉，右子树看到的 path 就会被左子树的残留污染。回溯算法的"回溯"二字，指的就是递归返回前撤销上一次的选择，让状态回到进入子树前的模样。

对比两个版本：算术版本里的cur是整数，按值传递，每一层递归都有自己的独立拷贝，天然不污染兄弟分支，所以不需要 pop。显式回溯版本因为引入了共享的可变结构，才必须手动撤销。理解了这一点，你就明白为什么很多回溯模板里总是"加入选择 -> 递归 -> 撤销选择"三件套了：不是模板非要有这步，而是因为状态结构是可变的。

个人建议：面试写这道题用算术版本，短、稳、不易错；课后练习时把回溯版本也写一遍，重点体会"撤销选择"的必要性。两者都掌握了，深搜和回溯之间的关系就不仅仅是一个概念，而是落到代码层面的直觉。

4. 两题对照表：什么时候该传参，什么时候该收结果

4.1 一张表看清方向差异

把这两道题的差异放到一张表里，谁该传参、谁该收结果一目了然：

为什么第6题不需要传参？因为它的信息完全存在于子树内部，节点之间不存在跨层累积状态；当前节点的答案只由孩子节点的结果决定，从根到当前节点一路发生了什么，与最终答案无关。而第7题是路径型问题，父节点留下的数字必须贯穿到叶子才能结算，所以参数里必须带着这份"家底"。

4.2 拿到二叉树题先问自己三个问题

我自己刷题时的习惯是，看到一道二叉树深搜题，不急着写代码，先在草稿纸上回答三个问题。

第一个问题：当前节点的答案，是由左右子树的答案拼出来的，还是需要在从根走过来的过程中维护出结果？前者走自底向上，递归应有返回值；后者走自顶向下，递归参数要带状态。这个判断定了，方向就不歪。

第二个问题：递归终止在哪里？是叶子节点，还是空节点，还是满足特定条件（比如值等于 target）？这直接决定递归函数体里的第一个判断写什么。很多运行时错误就是终止条件定错了，导致递归无休止地钻进 None。

第三个问题：递归到 None 时应该返回什么，才能不影响父层的合并逻辑？一般规律是：求和的返回 0，求最大/最小的返回负无穷/正无穷，求布尔与的返回 True，求布尔或的返回 False。这个"空值语义"想清楚了，边界条件就有一半写对了。

拿三道常见题验证这套流程。二叉树的最大深度：当前节点深度 = max(左子树深度, 右子树深度) + 1，明显是自底向上，返回值是子树深度。路径总和（是否存在根到叶的路径和等于 target）：走到当前节点时，剩余值需要传给子树，这是自顶向下带参数。对称二叉树：不是单方向传递，而是同时传入左节点和右节点，返回二者是否镜像相等，属于双子树同步递归。每种题目都能用"方向 + 终止 + 空值语义"这套框架套进去。

4.3 可以套用这两个套路的同类题目

第6题的"归并型"模板，可以迁移到表达式求值、判断平衡二叉树、二叉树的最大路径和这一类题。它们的共性是：当前节点的结果由左右子树结果组合而来，递归返回的是一个"子树级别的答案"。第7题的"传递型"模板，可以迁移到路径总和系列（112、113、437）、二叉树的所有路径（257）、求根到叶节点二进制数之和（1022）。共性是：每条路径都是一个累积状态，参数里带着状态往下走，到叶子时结算。

顺便提一句，二叉搜索树相关题目也大量使用深搜框架，只是多了一步"根据当前节点值和目标值的比较决定走哪棵子树"的剪枝；线索二叉树则是另一套利用空指针加速遍历的优化技巧，适合在递归深搜熟练之后再研究。刷题初期没必要所有概念一锅烩，先把"自顶向下传参"和"自底向上收结果"这两种姿势练成肌肉记忆，后面遇到啥题型都能快速归类。

5. 刷这组题时避不开的运行时错误与递归深度

5.1 'NoneType' has no attribute 'val' 到底错在哪

"写二叉树程序时为什么总是报运行时错误"是搜索热词里的高频问题，答案其实非常集中：绝大多数AttributeError: 'NoneType' object has no attribute 'val'都发生在你访问了可能为 None 的节点的属性。看这段错误代码：

def wrong_dfs(node): if node.left is None: # node 为 None 时，这里直接炸 return node.val == 1

明明 root 不是空，为什么递归进去 node 变成 None 了？因为你在叶子节点没有停住，继续调用了dfs(leaf.left)，下一层拿到的就是 None，再访问.left必然崩。正确的做法是让递归在空节点就返回，或者确保调用前节点一定非空。

排查这类错误有个固定三步：第一步，看 traceback 最后一个栈帧，定位在哪一行炸的；第二步，判断那一行的 node 是不是可能为 None，递归函数的参数来自哪里；第三步，在递归函数开头统一加if node is None: return xxx，或者调整上一层的调用逻辑，保证空节点不会进入函数主体。把这套流程走完，至少能消灭八成的二叉树运行时错误。

5.2 递归层数：链表化的树会教你做人

另一个刷题时容易撞上的运行时问题是RecursionError: maximum recursion depth exceeded。Python 默认递归深度上限是 1000，对于二叉树，递归深度等于树的高度。最坏情况下树退化成一条链表，高度等于节点数 n，只要 n 超过一千，递归栈就爆了。

处理办法有两个。第一，刷题场景下可以调高递归上限：

import sys sys.setrecursionlimit(10000)

这能解决测试数据不是极端深的情况。第二，如果数据规模真的很大，或者你在写生产代码，就得考虑把递归改成显式迭代栈。拿第7题举例，迭代版和递归版共享同一个"状态入栈"思想：

def sumNumbers(root): ans = 0 stack = [(root, 0)] while stack: node, cur = stack.pop() if node is None: continue cur = cur * 10 + node.val if node.left is None and node.right is None: ans += cur else: stack.append((node.left, cur)) stack.append((node.right, cur)) return ans

注意这里的cur是随着每个栈帧保存的，出栈时自动恢复各自路径的状态，完全不需要手动撤销。递归改迭代，本质就是把系统维护的调用栈换成你自己维护的显式栈，状态存哪里、怎么恢复，思路和回溯里的"撤销选择"如出一辙。

5.3 我的调试流程与心理预期

最后分享一点实战习惯。我做二叉树递归题，一旦运行结果不对，第一件事不是反复读代码，而是找一个最小样例，手动把递归调用树画出来，对比每个调用点的入参和返回值。比如第6题，画一棵只有三个节点的树，手动算一遍就发现某个叶子返回值是 0 而不是对应的布尔值，问题往往出在终止条件的类型上。第二件事是在递归入口加打印，最常见也最有效：

def dfs(node, cur): print(node.val if node else None, cur)

把完整调用过程打出来，错误逻辑在输出上无所遁形。

心理预期方面，得说句大实话：二叉树递归题刚开始写十次错十次完全正常。真正的问题不是"不会递归"，而是"没想清楚递归的输入输出就动手"。我现在的标准流程是：拿到题先写三条注释——递归返回值是什么、递归参数是什么、终止条件是什么——三条写清楚再碰键盘。这套流程坚持二十道题之后，你看到新题的第一反应会从"怎么递归"变成"这个题是什么方向"，到那时，深搜这关就算真正过了。

这两道题我强烈建议放在一起连着刷，一个练收，一个练传。把这两个方向吃透，再去碰路径总和、表达式求值、二叉树直径这类变形题，你会发现新题大多只是换了不同的状态定义和合并规则，骨架是完全一致的。如果能把第6题改成迭代版、把第7题写成回溯版，各做三遍，递归这条路上的坑基本就踩平了。