image.png

0. 鏈接

題目鏈接

1. 題目

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.

2. 思路1: BFS

1. 基本思路是:

• 利用隊列數(shù)據(jù)結構，存儲每一層的節(jié)點，及每個節(jié)點處的臨時計算結果
• 遵循BFS原則, 依次遍歷每一層的節(jié)點, 并計算此時的臨時計算結果, 當遍歷到葉子節(jié)點時, 將此時的臨時結果累加到返回值中

2. 分析:

• 過程中, 每個元素都被訪問1次
• 存儲空間最多占用的長度為葉子節(jié)點的數(shù)量, 對于一棵完全二叉樹而言, 占用空間最多, 為O(N); 對于一棵單分支二叉樹而言, 占用空間最少, 為O(1)

3. 復雜度

• 時間復雜度 O(N)
• 空間復雜度 最壞及平均O(N), 最好O(1)

3. 代碼

# coding:utf8
import collections


# 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 root is None:
            return 0

        rtn_sum = 0
        node_queue = collections.deque()
        sum_queue = collections.deque()

        node_queue.append(root)
        sum_queue.append(root.val)

        has_began = (root.val > 0)
        while len(node_queue) > 0:
            size = len(node_queue)
            for i in range(size):
                node = node_queue.popleft()
                value = sum_queue.popleft()

                if value > 0:
                    has_began = True
                ratio = 10 if has_began else 0
                if node.left is not None:
                    node_queue.append(node.left)
                    sum_queue.append(value * ratio + node.left.val)
                if node.right is not None:
                    node_queue.append(node.right)
                    sum_queue.append(value * ratio + node.right.val)
                if node.left is None and node.right is None:
                    rtn_sum += value

        return rtn_sum


solution = Solution()

root1 = node = TreeNode(1)
node.left = TreeNode(2)
node.right = TreeNode(3)
print('output1: {}'.format(solution.sumNumbers(root1)))

root2 = node = TreeNode(4)
node.left = TreeNode(9)
node.right = TreeNode(0)
node.left.left = TreeNode(5)
node.left.right = TreeNode(1)
print('output2: {}'.format(solution.sumNumbers(root2)))

root3 = node = TreeNode(1)
node.left = TreeNode(2)
node.left.left = TreeNode(3)
print('output3: {}'.format(solution.sumNumbers(root3)))

root4 = node = TreeNode(2)
print('output4: {}'.format(solution.sumNumbers(root4)))

root5 = node = TreeNode(0)
node.left = TreeNode(3)
node.right = TreeNode(0)
node.left.left = TreeNode(4)
print('output5: {}'.format(solution.sumNumbers(root5)))

輸出結果

output1: 25
output2: 1026
output3: 123
output4: 2
output5: 34

4. 結果

image.png