首页 > 代码库 > [leetcode]Sum Root to Leaf Numbers @ Python

[leetcode]Sum Root to Leaf Numbers @ Python

原题地址:http://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

题意:

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.

解题思路:看到二叉树,我们首先想到递归。比如一棵树如下:

                      1

                     /     \

                     2    3

                    /    \    /   \

                    4      5 6     7

     此题求和为sum=124+125+136+137,我们可以使用一个preSum变量来记录从根节点到节点父亲的路径,比如当我们递归的4时,preSum=12,递归到6时,preSum=13,这样就可以了。具体看代码。

代码:

# 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 sum(self, root, preSum):
        if root==None: return 0
        preSum = preSum*10 + root.val
        if root.left==None and root.right==None: return preSum
        return self.sum(root.left, preSum)+self.sum(root.right, preSum)
        
    def sumNumbers(self, root):
        return self.sum(root, 0)