题目描述
思路解析动画文字版
记住这套「进节点就 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题