算法题--二叉树各个分支构成的十进制数之和

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

基本思路是:

利用队列数据结构，存储每一层的节点，及每个节点处的临时计算结果
遵循BFS原则, 依次遍历每一层的节点, 并计算此时的临时计算结果, 当遍历到叶子节点时, 将此时的临时结果累加到返回值中

分析:

过程中, 每个元素都被访问1次
存储空间最多占用的长度为叶子节点的数量, 对于一棵完全二叉树而言, 占用空间最多, 为O(N); 对于一棵单分支二叉树而言, 占用空间最少, 为O(1)

复杂度

时间复杂度 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