LeetCode | 0129. 求根到叶子节点数字之和【Python】

叁歲伎倆 2023-01-04 14:45 143阅读 0赞

## Problem ##

[LeetCode][]

Given a binary tree containing digits from `0-9` only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path `1->2->3` which represents the number `123`.

Find the total sum of all root-to-leaf numbers.

**Note:** A leaf is a node with no children.

**Example:**

Input: [1,2,3]
        1
       / \
      2   3
    Output: 25
    Explanation:
    The root-to-leaf path 1->2 represents the number 12.
    The root-to-leaf path 1->3 represents the number 13.
    Therefore, sum = 12 + 13 = 25.

**Example 2:**

Input: [4,9,0,5,1]
        4
       / \
      9   0
     / \
    5   1
    Output: 1026
    Explanation:
    The root-to-leaf path 4->9->5 represents the number 495.
    The root-to-leaf path 4->9->1 represents the number 491.
    The root-to-leaf path 4->0 represents the number 40.
    Therefore, sum = 495 + 491 + 40 = 1026.

## 问题 ##

[力扣][Link 1]

给定一个二叉树，它的每个结点都存放一个 0-9 的数字，每条从根到叶子节点的路径都代表一个数字。

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

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

**说明:** 叶子节点是指没有子节点的节点。

**示例 1:**

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

**示例 2:**

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

## 思路 ##

**前序遍历**

想清楚 root 节点需要做的事：root值加上之前的值*10。
    不用深思递归细节，不然会乱的。

### Python3 代码 ###

# Definition for a binary tree node.
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    
    class Solution:
        def sumNumbers(self, root: TreeNode) -> int:
            def dfs(root: TreeNode, sumNumber: int) -> int:
                if not root:
                    return 0
                tmpsum = sumNumber * 10 + root.val
                # 叶子节点
                if not root.left and not root.right:
                    return tmpsum
                else:
                    return dfs(root.left, tmpsum) + dfs(root.right, tmpsum)
            
            return dfs(root, 0)

## GitHub 链接 ##

[Python][]

[LeetCode]: https://leetcode.com/problems/sum-root-to-leaf-numbers/
[Link 1]: https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
[Python]: https://github.com/Wonz5130/LeetCode-Solutions/blob/master/solutions/0129-Sum-Root-to-Leaf-Numbers/0129.py