• 難度： 中等
• 通過率： 40.6%
• 題目鏈接：. - 力扣（LeetCode）

題目描述

給定一個二叉樹，它的每個結點都存放一個?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.

解法：

深度優先遍歷。

class Solution:def sumNumbers(self, root: TreeNode) -> int:result = 0def dfs(node, num):nonlocal resultif not node:returnnum = num * 10 + node.valif (node.left is None) and (node.right is None):result += numreturndfs(node.left, num)dfs(node.right, num)dfs(root, 0)return result