Easy

题目描述

给你一个二叉树，每个节点的值不是 0 就是 1。每一条从根节点到叶节点的路径都代表一个从最高有效位开始的二进制数。

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

对于树中的每一片叶子，我们都要找出从根节点到该叶节点的路径所表示的数字。返回这些数字之和。

答案保证符合 32 位整数 范围。

示例 1：

输入：root = [1,0,1,0,1,0,1]
输出：22
解释：(100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

示例 2：

输入：root = [0]
输出：0

约束条件：

  • 树中节点的数目在 [1, 1000] 范围内
  • Node.val 只能是 0 或 1

解题思路

解题思路

这道题要求计算从根节点到每个叶节点路径表示的二进制数的和。有两种主要思路：

方法一：DFS + 路径记录

遍历所有从根到叶的路径，将每条路径转换为十进制数后求和。

方法二：DFS + 实时计算（推荐）

在遍历过程中实时计算当前路径的数值。当访问一个新节点时，将当前数值左移一位（乘以2）并加上当前节点值。这样避免了路径存储，更加高效。

核心思想是：对于二进制数，每向下一层，之前的数值要乘以2，再加上当前位的值。例如路径 1->0->1，计算过程为：

  • 到节点1：值为1
  • 到节点0：1*2+0=2
  • 到节点1：2*2+1=5

当到达叶节点时，累加当前路径值到总和中。

这种方法时间复杂度为O(n)，空间复杂度为O(h)，其中h是树的高度。

代码实现

class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        return dfs(root, 0);
    }
    
private:
    int dfs(TreeNode* node, int currentSum) {
        if (!node) return 0;
        
        currentSum = currentSum * 2 + node->val;
        
        if (!node->left && !node->right) {
            return currentSum;
        }
        
        return dfs(node->left, currentSum) + dfs(node->right, currentSum);
    }
};

class Solution:
    def sumRootToLeaf(self, root: Optional[TreeNode]) -> int:
        def dfs(node, current_sum):
            if not node:
                return 0
            
            current_sum = current_sum * 2 + node.val
            
            if not node.left and not node.right:
                return current_sum
            
            return dfs(node.left, current_sum) + dfs(node.right, current_sum)
        
        return dfs(root, 0)

public class Solution {
    public int SumRootToLeaf(TreeNode root) {
        return Dfs(root, 0);
    }
    
    private int Dfs(TreeNode node, int currentSum) {
        if (node == null) return 0;
        
        currentSum = currentSum * 2 + node.val;
        
        if (node.left == null && node.right == null) {
            return currentSum;
        }
        
        return Dfs(node.left, currentSum) + Dfs(node.right, currentSum);
    }
}

var sumRootToLeaf = function(root) {
    function dfs(node, currentSum) {
        if (!node) return 0;
        
        currentSum = currentSum * 2 + node.val;
        
        if (!node.left && !node.right) {
            return currentSum;
        }
        
        return dfs(node.left, currentSum) + dfs(node.right, currentSum);
    }
    
    return dfs(root, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要访问树中的每个节点一次，n为节点总数
空间复杂度O(h)递归调用栈的深度，h为树的高度，最坏情况下为O(n)