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

根到叶的路径，怎么读成一个二进制数

给一棵二叉树 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，左边走多远都不沾它。改成全局变量、回到岔路口忘了还原，右边就会接着左边的残值往下拼，答案整个偏掉。识别叶子也别退回去挨个问孩子空不空，一句引用相等更省，前提是非叶节点至少挂着一个孩子、必然不等。

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);
    }
}