LeetCode 1022简单树 · BST

从根到叶的二进制数之和图解题解

这道题到底在问什么

给定二叉树 root，每个节点值是 0 或 1。每条「根到叶」的路径，从最高有效位开始读，代表一个二进制数。求所有叶子对应二进制数之和（题目保证答案在 32 位整数范围内）。

输入: root=[1,0,1,0,1,0,1]
输出: 22

最优解：一步一步想明白

3记住这套「进节点就 cur 乘 2 加当前位、到叶子加进答案」，下面每一帧都在套它。
4cur=0, sum=0开局答案 sum 是 0，手里的二进制值 cur 也从 0 开始。DFS 这就从根往下探，每经过一个节点把 cur 乘 2 再加这个节点的位，到叶子时结算进 sum。
5读取 1走到这个节点，它的值是 1。进来时手里的 cur 还是 0，下一步要把这个 1 接到二进制数的末尾。
60×2+1=1把 cur 乘 2 再加上 1：0×2+1=1。这等于在二进制末尾追加一位 1，现在根到这里是 1，十进制就是 1。
7读取 0走到这个节点，它的值是 0。进来时手里的 cur 还是 1，下一步要把这个 0 接到二进制数的末尾。
81×2+0=2把 cur 乘 2 再加上 0：1×2+0=2。这等于在二进制末尾追加一位 0，现在根到这里是 10，十进制就是 2。
9读取 0走到这个节点，它的值是 0。进来时手里的 cur 还是 2，下一步要把这个 0 接到二进制数的末尾。
102×2+0=4把 cur 乘 2 再加上 0：2×2+0=4。这等于在二进制末尾追加一位 0，现在根到这里是 100，十进制就是 4。
11sum += 4 → 4这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 100，十进制 4。把它加进答案：sum 从 0 变成 4。
12cur 恢复 2左子树都结算完了，回到这个值为 0 的节点。注意 cur 又变回 2：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
13读取 1走到这个节点，它的值是 1。进来时手里的 cur 还是 2，下一步要把这个 1 接到二进制数的末尾。
142×2+1=5把 cur 乘 2 再加上 1：2×2+1=5。这等于在二进制末尾追加一位 1，现在根到这里是 101，十进制就是 5。
15sum += 5 → 9这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 101，十进制 5。把它加进答案：sum 从 4 变成 9。
16cur 恢复 1左子树都结算完了，回到这个值为 1 的节点。注意 cur 又变回 1：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
17读取 1走到这个节点，它的值是 1。进来时手里的 cur 还是 1，下一步要把这个 1 接到二进制数的末尾。
181×2+1=3把 cur 乘 2 再加上 1：1×2+1=3。这等于在二进制末尾追加一位 1，现在根到这里是 11，十进制就是 3。
19读取 0走到这个节点，它的值是 0。进来时手里的 cur 还是 3，下一步要把这个 0 接到二进制数的末尾。
203×2+0=6把 cur 乘 2 再加上 0：3×2+0=6。这等于在二进制末尾追加一位 0，现在根到这里是 110，十进制就是 6。
21sum += 6 → 15这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 110，十进制 6。把它加进答案：sum 从 9 变成 15。
22cur 恢复 3左子树都结算完了，回到这个值为 1 的节点。注意 cur 又变回 3：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
23读取 1走到这个节点，它的值是 1。进来时手里的 cur 还是 3，下一步要把这个 1 接到二进制数的末尾。
243×2+1=7把 cur 乘 2 再加上 1：3×2+1=7。这等于在二进制末尾追加一位 1，现在根到这里是 111，十进制就是 7。
25sum += 7 → 22这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 111，十进制 7。把它加进答案：sum 从 15 变成 22。
26答案 sum = 22四片叶子分别给出二进制 100、101、110、111，也就是 4、5、6、7。把它们加起来 4+5+6+7 等于 22，这就是答案。整个过程只是一次 DFS，沿途累积 cur、到叶子结算。

⚠️ 容易写错的地方

✗ 错：先把所有路径存下来再统一转十进制

✓ 对：边走边维护 cur=cur×2+val

沿途累积省掉额外存储，DFS 天然把每条路径分开

✗ 错：把 cur 当全局变量，回溯后忘了还原

✓ 对：cur 作为参数随递归传入

参数传值每条路径独立，不需要手动回退；全局变量才要小心还原

✗ 错：挨个判断左右孩子是否都空来识别叶子

✓ 对：代码用 left==right 一句判叶

叶子左右孩子都是空、引用相等；非叶至少一个孩子非空，必不相等

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        function<int(TreeNode*, int)> dfs = [&]( TreeNode* root, int x ) -> int {
            if (!root) {
                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);
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int x) {
        if (root == null) {
            return 0;
        }
        x = x << 1 | root.val;
        if (root.left == root.right) {
            return x;
        }
        return dfs(root.left, x) + dfs(root.right, x);
    }
}

复杂度

时间

O(n)

每个节点恰好访问一次，进出各做常数次运算

空间

O(h)

递归栈深等于树高 h；平衡时约 O(log n)，退化成链时最坏 O(n)

看不够？换成动画再走一遍

上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着从根到叶的二进制数之和的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。

看交互动画版 →更多图解题

面试官可能追问

为什么 cur×2 加节点值，就能从最高有效位开始拼出二进制？+

二进制是从最高位往低位读的。每深入一层，相当于把已经拼好的高位部分整体左移一位、空出最低位，再把这一层的 0 或 1 填进最低位。根在最高位、叶在最低位，正好对应题目说的「从最高有效位开始」。

节点数可达 1000，会不会溢出，递归会不会爆栈？+

题目已保证答案落在 32 位整数内，单条路径长度就是树高，位数有限，用 int 足够。递归深度等于树高，如果树退化成一条链，栈深可达 O(n)，担心爆栈可以改成显式栈的迭代写法，思路一样。

想听吴师兄把这道题讲给你听？

文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把从根到叶的二进制数之和一步步讲透（全站 0 节语音精讲，持续扩充），卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

LeetCode 1022简单树 · BST

从根到叶的二进制数之和图解题解

这道题到底在问什么

输入: root=[1,0,1,0,1,0,1]
输出: 22

最优解：一步一步想明白

3记住这套「进节点就 cur 乘 2 加当前位、到叶子加进答案」，下面每一帧都在套它。
4cur=0, sum=0开局答案 sum 是 0，手里的二进制值 cur 也从 0 开始。DFS 这就从根往下探，每经过一个节点把 cur 乘 2 再加这个节点的位，到叶子时结算进 sum。
5读取 1走到这个节点，它的值是 1。进来时手里的 cur 还是 0，下一步要把这个 1 接到二进制数的末尾。
60×2+1=1把 cur 乘 2 再加上 1：0×2+1=1。这等于在二进制末尾追加一位 1，现在根到这里是 1，十进制就是 1。
7读取 0走到这个节点，它的值是 0。进来时手里的 cur 还是 1，下一步要把这个 0 接到二进制数的末尾。
81×2+0=2把 cur 乘 2 再加上 0：1×2+0=2。这等于在二进制末尾追加一位 0，现在根到这里是 10，十进制就是 2。
9读取 0走到这个节点，它的值是 0。进来时手里的 cur 还是 2，下一步要把这个 0 接到二进制数的末尾。
102×2+0=4把 cur 乘 2 再加上 0：2×2+0=4。这等于在二进制末尾追加一位 0，现在根到这里是 100，十进制就是 4。
11sum += 4 → 4这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 100，十进制 4。把它加进答案：sum 从 0 变成 4。
12cur 恢复 2左子树都结算完了，回到这个值为 0 的节点。注意 cur 又变回 2：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
13读取 1走到这个节点，它的值是 1。进来时手里的 cur 还是 2，下一步要把这个 1 接到二进制数的末尾。
142×2+1=5把 cur 乘 2 再加上 1：2×2+1=5。这等于在二进制末尾追加一位 1，现在根到这里是 101，十进制就是 5。
15sum += 5 → 9这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 101，十进制 5。把它加进答案：sum 从 4 变成 9。
16cur 恢复 1左子树都结算完了，回到这个值为 1 的节点。注意 cur 又变回 1：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
17读取 1走到这个节点，它的值是 1。进来时手里的 cur 还是 1，下一步要把这个 1 接到二进制数的末尾。
181×2+1=3把 cur 乘 2 再加上 1：1×2+1=3。这等于在二进制末尾追加一位 1，现在根到这里是 11，十进制就是 3。
19读取 0走到这个节点，它的值是 0。进来时手里的 cur 还是 3，下一步要把这个 0 接到二进制数的末尾。
203×2+0=6把 cur 乘 2 再加上 0：3×2+0=6。这等于在二进制末尾追加一位 0，现在根到这里是 110，十进制就是 6。
21sum += 6 → 15这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 110，十进制 6。把它加进答案：sum 从 9 变成 15。
22cur 恢复 3左子树都结算完了，回到这个值为 1 的节点。注意 cur 又变回 3：因为 cur 是顺着参数往下传的，每条路径各算各的，左边走过完全不影响右边。接着走右孩子。
23读取 1走到这个节点，它的值是 1。进来时手里的 cur 还是 3，下一步要把这个 1 接到二进制数的末尾。
243×2+1=7把 cur 乘 2 再加上 1：3×2+1=7。这等于在二进制末尾追加一位 1，现在根到这里是 111，十进制就是 7。
25sum += 7 → 22这个节点没有孩子，是叶子，路径读完了。根到它的二进制是 111，十进制 7。把它加进答案：sum 从 15 变成 22。
26答案 sum = 22四片叶子分别给出二进制 100、101、110、111，也就是 4、5、6、7。把它们加起来 4+5+6+7 等于 22，这就是答案。整个过程只是一次 DFS，沿途累积 cur、到叶子结算。

⚠️ 容易写错的地方

✗ 错：先把所有路径存下来再统一转十进制

✓ 对：边走边维护 cur=cur×2+val

沿途累积省掉额外存储，DFS 天然把每条路径分开

✗ 错：把 cur 当全局变量，回溯后忘了还原

✓ 对：cur 作为参数随递归传入

参数传值每条路径独立，不需要手动回退；全局变量才要小心还原

✗ 错：挨个判断左右孩子是否都空来识别叶子

✓ 对：代码用 left==right 一句判叶

叶子左右孩子都是空、引用相等；非叶至少一个孩子非空，必不相等

完整代码（Python / C++ / Java）

Python

from __future__ import annotations
from 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 = right
class 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 = right
class 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)

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        function<int(TreeNode*, int)> dfs = [&]( TreeNode* root, int x ) -> int {
            if (!root) {
                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);
    }
};

Java

import java.util.*;
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode root, int x) {
        if (root == null) {
            return 0;
        }
        x = x << 1 | root.val;
        if (root.left == root.right) {
            return x;
        }
        return dfs(root.left, x) + dfs(root.right, x);
    }
}

复杂度

时间

O(n)

每个节点恰好访问一次，进出各做常数次运算

空间

O(h)

递归栈深等于树高 h；平衡时约 O(log n)，退化成链时最坏 O(n)

看不够？换成动画再走一遍

看交互动画版 →更多图解题

面试官可能追问

为什么 cur×2 加节点值，就能从最高有效位开始拼出二进制？+

节点数可达 1000，会不会溢出，递归会不会爆栈？+

想听吴师兄把这道题讲给你听？

¥99 开通图解算法年卡 →先去动画页听 30 秒试听 →

从根到叶的二进制数之和 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

从根到叶的二进制数之和 图解题解

这道题到底在问什么

最优解：一步一步想明白

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

Python

C++

Java

复杂度

看不够？换成动画再走一遍

面试官可能追问

想听吴师兄把这道题讲给你听？

从根到叶的二进制数之和图解题解

从根到叶的二进制数之和图解题解