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.
For example,
1
/
2 3
- The root-to-leaf path 1->2 represents the number 12.
- The root-to-leaf path 1->3 represents the number 13.
- Return the sum = 12 + 13 = 25.
Python Solution:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root: return 0
cur = []
res = [0]
def preorder(root):
cur.append(str(root.val))
if not root.left and not root.right:
res[0] += int(''.join(cur))
if root.left: preorder(root.left)
if root.right: preorder(root.right)
cur.pop()
preorder(root)
return res[0]
Python Solution 2:
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sumNumbers(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def preorder(root, sum):
if not root: return 0
val = sum * 10 + root.val
if not root.left and not root.right:
return val
return preorder(root.left, val) + preorder(root.right, val)
return preorder(root, 0)
Summary:
- Solution 2 is much better.
LeetCode: 129. Sum Root to Leaf Numbers
近期评论