0129. 求根节点到叶节点数字之和【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - DFS

1. 📝 题目描述

• leetcode

给你一个二叉树的根节点 root，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123。

计算从根节点到叶节点生成的 所有数字之和。

叶节点 是指没有子节点的节点。

---

示例 1：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

示例 2：

输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

---

提示：

• 树中节点的数目在范围 [1, 1000] 内
• 0 <= Node.val <= 9
• 树的深度不超过 10

2. 🎯 s.1 - DFS

c

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
int dfs(struct TreeNode* node, int num) {
    if (!node) return 0;
    num = num * 10 + node->val;
    if (!node->left && !node->right) return num;
    return dfs(node->left, num) + dfs(node->right, num);
}

int sumNumbers(struct TreeNode* root) {
    return dfs(root, 0);
}

js

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var sumNumbers = function (root) {
  function dfs(node, num) {
    if (!node) return 0
    num = num * 10 + node.val
    if (!node.left && !node.right) return num
    return dfs(node.left, num) + dfs(node.right, num)
  }
  return dfs(root, 0)
}

py

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def dfs(node, num):
            if not node:
                return 0
            num = num * 10 + node.val
            if not node.left and not node.right:
                return num
            return dfs(node.left, num) + dfs(node.right, num)
        return dfs(root, 0)

• 时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数
• 空间复杂度：$O(h)$，其中 $h$ 是二叉树的高度，递归调用栈的深度

算法思路：

• 从根节点开始 DFS，每次将父节点传下来的数字乘以 10 再加上当前节点值
• 到达叶子节点时返回当前数字，非叶子节点返回左右子树结果之和