|
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 = Noneclass
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.
【LeetCode OJ】Sum Root to Leaf Numbers,布布扣,bubuko.com
【LeetCode OJ】Sum Root to Leaf Numbers
原文：http://www.cnblogs.com/zzzdevil/p/3704758.html