题目描述
思路解析
一句话答案：LeetCode 1022 从根到叶的二进制数之和：每条根到叶路径读成一个二进制数，DFS 带累积值 cur、每下一层 cur 乘 2 再并上当前位，到叶子结算，时间 O(n)、空间 O(h)。
根到叶的路径，怎么读成一个二进制数
给一棵二叉树 root，每个节点的值不是 0 就是 1。从根一路走到某片叶子，把沿途的位按先后连起来，就是一个二进制数，最上面的根是最高位、最下面的叶是最低位。要求把每片叶子对应的那个数全加起来。题面例子 root=[1,0,1,0,1,0,1]，四条根到叶路径分别读出 100、101、110、111，也就是 4、5、6、7，加起来 22。
先把整条路径存下来再转十进制，差在哪
位数最多和树高一样，看着不长，于是容易想着先 DFS 把每条根到叶的路径收成一串 0 和 1，再逐串换算成十进制相加。这样得为每条路径单开一块存储，走完还要再遍历一遍做换算。其实需要留在手里的只有一个当前值，边走边算就够，没必要把整条路径攒着。
二进制从高位读，深入一层就左移一位
二进制数是从最高位往低位读的。已经拼到手的高位，每往下深入一层，相当于整体左移一位、空出最低位，再把这一层的 0 或 1 填进去。所以维护一个累积值 cur：进入一个节点时，cur 乘 2 就是左移一位，再加上这个节点的位。根对应最高位、叶对应最低位，一路拼到叶子，cur 正好是这条路径读出的数。
递归到每个节点做什么、又返回什么
写成递归 dfs(node, cur)：进来先更新 cur，让它乘 2 再加上 node 的值。接着判断是不是叶子——代码用 node 的左孩子和右孩子引用相等这一句来判定，因为叶子左右都是空、两个空引用恰好相等；只要有一个孩子还在，就不相等。是叶子，这条路径读完了，直接返回当前的 cur。不是叶子，就返回左子树和右子树两次递归结果之和。总和靠层层返回值相加汇总上来，不用额外开全局变量去累计。
拿 [1,0,1,0,1,0,1] 把四条路径都拼一遍
根是 1，进来 cur 从 0 变成 0 乘 2 加 1，等于 1。往左走到 0：cur 变成 1 乘 2 加 0，等于 2。再往左到叶子 0：cur 变成 2 乘 2 加 0，等于 4——这条路径 100 读出 4，返回 4。退回上一个 0，那层 cur 还是 2，改走右孩子 1：cur 变成 2 乘 2 加 1，等于 5，是叶子返回 5。
根的右半边同理。根传下来的 cur 是 1，走到右孩子 1：cur 变成 1 乘 2 加 1，等于 3。往左到叶子 0：3 乘 2 加 0 等于 6，返回 6；退回后走右孩子 1：3 乘 2 加 1 等于 7，返回 7。四片叶子交回 4、5、6、7，一层层加上去，4 加 5 加 6 加 7 得 22。
只走一遍的开销，传值和认叶别搞混
每个节点只在递归里访问一次，进出各做几步常数运算，时间就是 O(n)，n 是节点数。额外空间是递归栈，深度等于当前路径长度、也就是树高 h；匀称时约 log n 级，长成单链最坏到 O(n)。
cur 一定要当参数传，靠的正是参数各走各的：右孩子拿到的是岔路口那层的 cur，左边走多远都不沾它。改成全局变量、回到岔路口忘了还原，右边就会接着左边的残值往下拼，答案整个偏掉。识别叶子也别退回去挨个问孩子空不空，一句引用相等更省，前提是非叶节点至少挂着一个孩子、必然不等。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这套「进节点就 cur 乘 2 加当前位、到叶子加进答案」，下面每一帧都在套它。
准备 · 从根出发：开局答案 sum 是 0，手里的二进制值 cur 也从 0 开始。DFS 这就从根往下探，每经过一个节点把 cur 乘 2 再加这个节点的位，到叶子时结算进 sum。
到达节点 1：走到这个节点，它的值是 1。进来时手里的 cur 还是 0，下一步要把这个 1 接到二进制数的末尾。
累积 cur = 1：把 cur 乘 2 再加上 1：0×2+1=1。这等于在二进制末尾追加一位 1，现在根到这里是 1，十进制就是 1。
到达节点 0：走到这个节点，它的值是 0。进来时手里的 cur 还是 1，下一步要把这个 0 接到二进制数的末尾。
累积 cur = 2：把 cur 乘 2 再加上 0：1×2+0=2。这等于在二进制末尾追加一位 0，现在根到这里是 10，十进制就是 2。
到达节点 0：走到这个节点，它的值是 0。进来时手里的 cur 还是 2，下一步要把这个 0 接到二进制数的末尾。
累积 cur = 4：把 cur 乘 2 再加上 0：2×2+0=4。这等于在二进制末尾追加一位 0，现在根到这里是 100，十进制就是 4。
叶子结算 sum = 4：这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 100，十进制 4。把它加进答案：sum 从 0 变成 4。
回到节点 0：左子树都结算完了，回到这个值为 0 的节点。注意 cur 又变回 2：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
到达节点 1：走到这个节点，它的值是 1。进来时手里的 cur 还是 2，下一步要把这个 1 接到二进制数的末尾。
累积 cur = 5：把 cur 乘 2 再加上 1：2×2+1=5。这等于在二进制末尾追加一位 1，现在根到这里是 101，十进制就是 5。
叶子结算 sum = 9：这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 101，十进制 5。把它加进答案：sum 从 4 变成 9。
回到节点 1：左子树都结算完了，回到这个值为 1 的节点。注意 cur 又变回 1：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
到达节点 1：走到这个节点，它的值是 1。进来时手里的 cur 还是 1，下一步要把这个 1 接到二进制数的末尾。
累积 cur = 3：把 cur 乘 2 再加上 1：1×2+1=3。这等于在二进制末尾追加一位 1，现在根到这里是 11，十进制就是 3。
到达节点 0：走到这个节点，它的值是 0。进来时手里的 cur 还是 3，下一步要把这个 0 接到二进制数的末尾。
累积 cur = 6：把 cur 乘 2 再加上 0：3×2+0=6。这等于在二进制末尾追加一位 0，现在根到这里是 110，十进制就是 6。
叶子结算 sum = 15：这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 110，十进制 6。把它加进答案：sum 从 9 变成 15。
回到节点 1：左子树都结算完了，回到这个值为 1 的节点。注意 cur 又变回 3：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
到达节点 1：走到这个节点，它的值是 1。进来时手里的 cur 还是 3，下一步要把这个 1 接到二进制数的末尾。
累积 cur = 7：把 cur 乘 2 再加上 1：3×2+1=7。这等于在二进制末尾追加一位 1，现在根到这里是 111，十进制就是 7。
叶子结算 sum = 22：这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 111，十进制 7。把它加进答案：sum 从 15 变成 22。
完成：四片叶子分别给出二进制 100、101、110、111，也就是 4、5、6、7。把它们加起来 4+5+6+7 等于 22，这就是答案。整个过程只是一次 DFS，沿途累积 cur、到叶子结算。
边界先想清：单节点直接成数；上面这棵四条路径全是 001，加起来 4。
面试重点：讲清 cur×2 加位为何对应「最高位开始」，以及溢出与栈深这两点。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Definition for a binary tree node.# class TreeNode:# def __init__(self, val=0, left=None, right=None):# self.val = val# self.left = left# self.right = rightclass Solution: def sumRootToLeaf(self, root: Optional[TreeNode]) -> int: def dfs(root: Optional[TreeNode], x: int) -> int: if root is None: return 0 x = x << 1 | root.val if root.left == root.right: return x return dfs(root.left, x) + dfs(root.right, x) return dfs(root, 0)复杂度
- 时间：O(n)，每个节点恰好访问一次，进出各做常数次运算
- 空间：O(h)，递归栈深等于树高 h；平衡时约 O(log n)，退化成链时最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么 cur×2 加节点值，就能从最高有效位开始拼出二进制？
追问节点数可达 1000，会不会溢出，递归会不会爆栈？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
找出克隆二叉树中的相同节点
LeetCode 1379 · 简单 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题