给定一个二叉树，它的每个结点都存放一个 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.

解法一：递归

  1. class Solution:
  2.     def sumNumbers(self, root: TreeNode) -> int:
  3.         ans = 0
  4.         def dfs(root, prev_total):
  5.             nonlocal ans
  6.             if root:
  7.                 if not root.left and not root.right:
  8.                     ans += prev_total * 10 + root.val
  9.                 if root.left:
  10.                     dfs(root.left, prev_total * 10 + root.val)
  11.                 if root.right:
  12.                     dfs(root.right, prev_total * 10 + root.val)
  13.         dfs(root, 0)
  14.         return ans

解法二：迭代+重建路径

  1. class Solution:
  2.     def sumNumbers(self, root: TreeNode) -> int:
  3.         stack = [root] if root else []
  4.         ans = 0
  5.         parents = {root: None}
  6.         while stack:
  7.             node = stack.pop()
  8.             if not node.left and not node.right:
  9.                 i = 0
  10.                 cur = node
  11.                 while cur:
  12.                     ans += cur.val * 10**i
  13.                     cur = parents[cur]
  14.                     i += 1
  15.             if node.left:
  16.                 stack.append(node.left)
  17.                 parents[node.left] = node
  18.             if node.right:
  19.                 stack.append(node.right)
  20.                 parents[node.right] = node
  21.         return ans

解法三：迭代+DP

只需要记录root到当前节点的累加和即可，不需要重建完整路径。

  1. class Solution:
  2.     def sumNumbers(self, root: TreeNode) -> int:
  3.         if not root:
  4.             return 0
  5.         stack, dp = [root], {root: root.val}
  6.         ans = 0
  7.         while stack:
  8.             node = stack.pop()
  9.             if not node.left and not node.right:
  10.                 ans += dp[node]
  11.             if node.left:
  12.                 stack.append(node.left)
  13.                 dp[node.left] = dp[node] * 10 + node.left.val
  14.             if node.right:
  15.                 stack.append(node.right)
  16.                 dp[node.right] = dp[node] * 10 + node.right.val
  17.         return ans