首页 > 代码库 > 【LeetCode OJ】Sum Root to Leaf Numbers

【LeetCode OJ】Sum Root to Leaf Numbers

2024-07-02 15:48:13   230人阅读

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
 
class Solution:
    # @param root, a tree node
    # @return an integer
    def sumNumbers(self, root):
        """
        BFS the tree from the root
        track each path as a root->leaf number
        """
        # specail cases
        if root is None:
            return 0
 
        # queue of the numbers
        # BSF the tree
        q = [ (root, 0) ]
        res = 0
        while q:
            new_q = []
            # expand all paths in q by one step
            for (node, number) in q:
                node_number = number * 10 + node.val
                # If the node is a leaf, remove this path and record the root-leaf number
                if node.left == node.right == None:
                    res += node_number
                # Expand the path by left/right children
                else:
                    if node.left:
                        new_q.append( (node.left, node_number) )
                    if node.right:
                        new_q.append( (node.right, node_number) )
            # Update the path list
            q = new_q
             
        return res
           

 

Problem Link:

http://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

This problem is easy to solve by using BFS from the tree root.

We use a list to keep track of different paths, where each path is represented as a number.

 


联系
我们