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

约 4 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 虾皮
标签
深度优先搜索 树 二叉树

题目描述

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

image-20260929073548141

image-20260929073548260

image-20260929073548417

题意分析

每个节点值是二进制位 0 或 1，一条从根到叶的路径按经过顺序组成一个二进制整数，根是最高位，叶子是最低位。要求把所有完整路径对应的数值相加。

路径上的位需要按位置拼接，不是把节点值简单相加。只有左右孩子都为空才是叶子；到达内部节点时得到的只是数字前缀，不能提前计入总和。

解法：DFS 累积路径值

核心思路

[!blue]

已有二进制数值末尾追加一位，相当于让原来的每一位向左移动，再把新位填到最低位。因此从路径前缀 prefix 到当前节点的数值是 prefix * 2 + node.val，也可以写成 (prefix << 1) | node.val，左移后的最低位为零，所以按位或正好等价于加入这一位。

定义递归参数 prefix 为从根到当前节点父亲形成的数值，尚未包含当前位。进入节点后先计算 value，它才是根到当前节点的完整前缀。

空节点代表这侧没有路径，贡献为 0；叶子代表一条路径已经完成，返回 value；非叶子则把 value 分别传给左右孩子，再将两侧的完整路径贡献相加。左右子树的路径集合互不重叠，合并后恰好包含当前节点之下的全部根到叶路径。

从根前的空前缀 0 开始。整数参数按值传递，左分支的更新不会改动右分支要使用的前缀，因此无需构造字符串，也不需要共享可变路径或额外回滚。

解题步骤

  1. 调用 dfs(root, 0)，空节点直接返回 0。
  2. 当前节点存在时，左移前缀并加入当前二进制位，得到 value。
  3. 若左右孩子都为空，返回这一条完整路径的数值。
  4. 否则用同一个 value 递归两侧，返回左右结果之和。

代码实现

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

    // prefix 表示根到父节点的路径值，尚未包含当前节点。
    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
    // prefix 表示根到父节点的路径值，尚未包含当前节点。
    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 为树高，来自递归栈。

关键点总结

[!green]

  • 左移再加当前位体现二进制位权，路径越深，已有前缀的位权继续提高。
  • 参数传递一条路径的前缀，返回值汇总这棵子树下的完整路径，两者含义不同。
  • 空子树不产生路径，叶子才结算，中间节点只负责扩展并合并。

易错点总结

[!yellow]

  • 用节点值直接相加，会丢掉根到叶顺序对应的二进制位权。
  • 先按位或再左移，会把新加入的最低位也整体左移，得到错误数值。
  • 任意一个孩子为空就判为叶子，会提前停止只有单侧孩子的路径。
  • 每进入一个节点都累加当前前缀，会把未结束的短路径也加入答案。
  • 给孩子继续传旧 prefix 而不是 value，会漏掉当前节点的位。

相似题目

题目 难度 关联与区别
129. 求根节点到叶节点数字之和 中等 根到叶数值累积相同，本题每层乘2加当前位，原题每层乘10。
112. 路径总和 简单 同样遍历根到叶路径，但本题路径状态是按位形成的数，不是简单的节点和。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/32522316
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！