LeetCode 1022. 从根到叶的二进制数之和

2022-05-18 HGNULB 约 5 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1022. 从根到叶的二进制数之和

题意分析

给一棵每个节点值只能是 0 或 1 的二叉树，从根走到任意一个叶子会得到一串 0/1，把它当作二进制数（根是最高位、叶子是最低位），求所有根到叶路径对应数值的总和。

要点有三个。第一，路径必须从根开始、到叶子结束，中间节点不产生答案——这决定了「什么时候结算」这个关键判断只能写在叶子处。第二，值只有 0 和 1，说明不需要考虑进位或多位数字的拼接，每下降一层就是把已有的值左移一位再加上当前位。第三，求的是「总和」而不是「所有路径的列表」，所以不必真的把路径存下来，边走边累加即可，省掉一个 $O(\text{高度})$ 的容器。

约束是节点数在 [1, 1000]，树高不超过 1000，且明确说明答案不超过 32 位整数范围。前者提示递归深度在极端链式树下会接近 1000，Java 默认栈能扛住但值得心里有数；后者让我们可以放心用 int 累加，不必上 long。

边界只有一处需要认真对待：叶子的定义是左右子树都为空，而不是「某一边为空」。一个只有左孩子的节点不是叶子，如果在这里就结算，会凭空造出一条不存在的路径。至于空树，题目保证至少有一个节点，但让代码自然返回 0 仍然是更好的实现。

解法：DFS 累积路径值

核心思路

不必保存路径。二进制数末尾追加一位 bit，数值会变为 value * 2 + bit，也就是 (value << 1) | bit。因此 DFS 时只需携带一个整数 prefix。

定义 dfs(node, prefix)：prefix 是从根到 node 父节点的路径值，返回 node 子树内所有完整根到叶路径的数值之和。进入节点后先计算：

value = (prefix << 1) | node.val

若当前节点是叶子，这条路径已经完整，直接返回 value；否则返回左右子树贡献之和。空孩子返回 0，既不会产生伪路径，也能让单孩子节点沿真实孩子继续搜索。

不变量：每次进入 dfs 时，prefix 恰好编码了当前节点之前的全部路径位。处理当前位后，value 就恰好编码根到当前节点的路径。参数按值传递，所以左右分支互不污染，不需要显式回溯。

正确性：叶子处返回的正是该根到叶二进制数。对非叶节点，完整路径必然且只会进入左、右子树之一；根据归纳假设，两次递归分别得到两侧所有路径之和，相加便是不重不漏的答案。

解题步骤

从根开始调用 dfs(root, 0)。

空节点返回 0；否则用左移和按位或把当前位追加到 prefix。

只有左右孩子都为空时才结算，返回当前路径值。

非叶节点分别递归左右孩子，并返回两侧贡献之和。

样例 [1,0,1,0,1,0,1] 的四条路径依次表示 100(4)、101(5)、110(6)、111(7)，总和为 22。

边界反例：链 1 -> 1 -> 1 只有一条路径，答案是二进制 111 = 7。若用 left == null || right == null 判断叶子，根和中间节点也会被提前结算。

代码实现

class Solution {
    public int sumRootToLeaf(TreeNode root) {
        return dfs(root, 0);
    }

    private int dfs(TreeNode node, int prefix) {
        if (node == null) {
            return 0;
        }
        int value = (prefix << 1) | node.val;
        if (node.left == null && node.right == null) {
            return value;
        }
        return dfs(node.left, value) + dfs(node.right, value);
    }
}

func sumRootToLeaf(root *TreeNode) int {
	var dfs func(*TreeNode, int) int
	dfs = func(node *TreeNode, prefix int) int {
		if node == nil {
			return 0
		}
		value := (prefix << 1) | node.Val
		if node.Left == nil && node.Right == nil {
			return value
		}
		return dfs(node.Left, value) + dfs(node.Right, value)
	}
	return dfs(root, 0)
}

复杂度分析

时间复杂度：$O(n)$，每个节点只访问一次。

空间复杂度：$O(h)$，h 为树高，来自递归栈；平衡树为 $O(\log n)$，链式树最坏为 $O(n)$。

关键点总结

路径只用于计算数值时，传递聚合状态即可，不要物化字符串或列表。

追加二进制位的递推式是 value = (prefix << 1) | bit；推广到 k 进制就是 prefix * k + digit。

递归参数按值传递，分支之间天然隔离；递归返回值则直接表达子树贡献，避免可变的全局累加器。

只在真正叶子处结算，单孩子节点仍是中间节点。

易错点总结

叶子条件误写成 left == null || right == null：链 1 -> 1 -> 1 会在中途提前结算；必须左右都为空。

在每个节点都累加：样例会把中间前缀 1、10、11 也计入，得到 28 而非 22。

写成 (prefix | node.val) << 1：这会先追加再整体左移，叶子位恒为 0；操作顺序必须是先左移再放当前位。

用共享成员变量保存路径值却不回溯：走完左子树后会污染右子树。把路径值作为参数传递即可。

Go 的递归闭包不能直接用 dfs := func(...) 并在函数体中调用自身；应先声明函数变量，再赋值。

相似题目

题目	难度	考察点
129. 求根节点到叶节点数字之和	中等	完全同构，只是进制从二进制换成十进制，递推式变成 `cur * 10 + val`
LCR 049. 求根节点到叶节点数字之和	中等	与 129 同题，可直接套用本文的参数传值骨架
112. 路径总和	简单	下传的是剩余目标值而非累积值，且只需返回是否存在，可提前短路返回
113. 路径总和 II	中等	要求输出路径本身，必须真的维护列表，因而需要手写回溯撤销
257. 二叉树的所有路径	简单	聚合值是字符串拼接，注意分隔符只在非首节点前添加
404. 左叶子之和	简单	结算条件需要父节点提供「我是左孩子」的信息，判据不只看节点自身
剑指 Offer 34. 二叉树中和为某一值的路径	中等	与 113 同题，常被追问「路径不必从根开始」的变体（437 题）如何改写