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
- 基本思路是:
- 利用隊列數(shù)據(jù)結(jié)構(gòu)御毅，存儲每一層的節(jié)點，及每個節(jié)點處的臨時計算結(jié)果
- 遵循BFS原則, 依次遍歷每一層的節(jié)點, 并計算此時的臨時計算結(jié)果, 當(dāng)遍歷到葉子節(jié)點時, 將此時的臨時結(jié)果累加到返回值中
- 分析:
- 過程中, 每個元素都被訪問1次
- 存儲空間最多占用的長度為葉子節(jié)點的數(shù)量, 對于一棵完全二叉樹而言, 占用空間最多, 為O(N); 對于一棵單分支二叉樹而言, 占用空間最少, 為O(1)
- 復(fù)雜度
- 時間復(fù)雜度
O(N) - 空間復(fù)雜度 最壞及平均
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)))
輸出結(jié)果
output1: 25
output2: 1026
output3: 123
output4: 2
output5: 34
4. 結(jié)果
image.png
