leetcode 2026-02-24 每日一练 - 从根到叶的二进制数之和

Austoin2026-02-242026-02-24

今天开始记录leetcode的每日一练和其他题目编写思路与过程。

题目描述

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

给出一棵二叉树，其上每个结点的值都是 0 或 1。每一条从根到叶的路径都代表一个从最高有效位开始的二进制数。

例如，如果路径为 0 -> 1 -> 1 -> 0 -> 1，那么它表示二进制数 01101，也就是 13。

对树上的每一片叶子，我们都要找出从根到该叶子的路径所表示的数字。

返回这些数字之和。题目数据保证答案是一个 32 位整数。

解题思路

根节点到叶子节点的数字之和，就是根节点到叶子节点的二进制数之和。

核心思路是使用深度优先搜索（DFS）遍历二叉树，在遍历过程中：

每向下走一层，当前数字左移一位（相当于乘以2）
将当前节点的值加入到数字中（通过位运算 | 操作）
到达叶子节点时，将该路径表示的数字累加到结果中

代码实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumRootToLeaf(root *TreeNode) (ans int) {
    var dfs func(*TreeNode, int)
    dfs = func(node *TreeNode, num int) {
        if node == nil {
            return
        }
        // 左移一位并加上当前节点值
        num = num << 1 | node.Val
        // 到达叶子节点，累加结果
        if node.Left == nil && node.Right == nil {
            ans += num
            return
        }
        // 递归遍历左右子树
        dfs(node.Left, num)
        dfs(node.Right, num)
    }
    dfs(root, 0)
    return
}