给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字：

例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。 计算从根节点到叶节点生成的 所有数字之和 。

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

---

深度优先遍历

# 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: TreeNode) -> int:
        def helper(root, pre_total):
            if not root:
                return 0
            total = pre_total*10 + root.val
            if not root.left and not root.right:
                return total
            else:
                return helper(root.left, total) + helper(root.right, total)
        return helper(root, 0)

广度优先遍历

# 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: TreeNode) -> int:
        if not root:
            return 0
        
        node_queue = collections.deque([root])
        num_queue = collections.deque([root.val])
        total = 0
        while node_queue:
            node = node_queue.popleft()
            num = num_queue.popleft()
            if not node.left and not node.right:
                total += num
            else:
                if node.left:
                    node_queue.append(node.left)
                    num_queue.append(num*10+node.left.val)
                if node.right:
                    node_queue.append(node.right)
                    num_queue.append(num*10+node.right.val)
        return total