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

从根到叶的二进制数之和

🎯 问题描述

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

💻 解题思路

思路一：字符串拼接法（直观易懂）

在 DFS 过程中将节点值拼接成二进制字符串，到达叶子节点时使用 int(string, 2) 转换为十进制。

• 优点：代码极其直观，符合人类阅读二进制数的习惯。
• 缺点：字符串拼接会产生大量临时对象，且每次转换都需要重新计算，效率较低。

思路二：位运算动态维护（最优解）

在 DFS 过程中，每向下走一层，就将当前的十进制数值左移一位（乘以 2），再加上当前节点的值。

• 公式：cur_val = (cur_val << 1) | node.val 或 cur_val = cur_val * 2 + node.val。
• 优点：直接在数字层面进行运算，时间复杂度和空间复杂度都达到最优。

代码实现

from typing import Optional

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, cr):
            if not node:
                return 
            
            # 动态更新当前的十进制数值
            cr = (cr << 1) | node.val
            
            nonlocal ans
            if not node.left and not node.right:
                ans += cr
                return
            
            dfs(node.left, cr)
            dfs(node.right, cr)
        
        dfs(root, 0)
        return ans

📊 性能分析

• 时间复杂度：$O(n)$。每个节点只被访问一次，且每次访问只进行常数时间的位运算。
• 空间复杂度：$O(h)$。递归栈的空间开销，取决于二叉树的高度。

💡 思考

这道题与 LeetCode 129（求根节点到叶节点数字之和）的解题逻辑几乎一模一样。

• 十进制拼接：cr = cr * 10 + node.val
• 二进制拼接：cr = cr * 2 + node.val （即 cr = (cr << 1) | node.val）
  掌握这种“在递归传参中动态维护路径状态”的方法，就能通杀这一类题目。