[题目描述]
[代码思路]
做这道题首先想到的, 就是遍历这棵树的所有根结点到叶结点的路径, 将每条路径的和保存在一个 list 中, 最后看 list 中是否含有题目给定的数据即可. 遍历一棵树的所有路径, 一定是要用到深度优先, 写递归函数的, 那么还是抓住一个点去看, 就拿 5 这个结点来看, 当递归函数输入的结点是 5.
那么我首先是要去判断这个结点是否有左右子树的, 用一个变量 sum1 存放一路总和. 我的递归函数是 plus(root,sum1); 如果有左子树, 那么调用 plus(root,sum1+5); 如果有右子树, 那么调用 plus(root,sum1+5); 有左右子树调用递归函数传入的 sum1 数值应该是一致的, 都是 sum1+root.val.
- if root.left:
- self.plus(root.left,sum1+root.val)
- if root.right:
- self.plus(root.right,sum1+root.val)
如果这个结点没有左右子树了, 说明是叶结点了, 那么就直接加上该叶结点的数值, 把这个 sum1 存在 list 中就好了.
- if not root.left and not root.right:
- sum1+=root.val
- print "叶结点:",root.val,"sum1=",sum1
- self.sum_list.append(sum1)
在主调函数中调用这个 plus 递归函数, 我定义 sum_list 为类的一个属性, 所以在类内部可直接通过 self.sum_list 读写.
- def __init__(self):
- self.sum_list=[]
在主调函数中再判断一下, sum 是否包含在 sum_list 中即可
- def hasPathSum(self, root, sum):
- """
- :type root: TreeNode
- :type sum: int
- :rtype: bool
- """
- sum1=0
- if not root:return False
- self.plus(root,sum1)
- return sum in self.sum_list
[源代码]
- # 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 __init__(self):
- self.sum_list=[]
- def hasPathSum(self, root, sum):
- """
- :type root: TreeNode
- :type sum: int
- :rtype: bool
- """
- sum1=0
- if not root:return False
- self.plus(root,sum1)
- return sum in self.sum_list
- def plus(self,root,sum1):
- print "执行 plus(",root.val,sum1,")"
- if not root.left and not root.right:
- sum1+=root.val
- print "叶结点:",root.val,"sum1=",sum1
- self.sum_list.append(sum1)
- if root.left:
- self.plus(root.left,sum1+root.val)
- if root.right:
- self.plus(root.right,sum1+root.val)
- return False
[递归过程重现]
为了更好理解, 我以一棵树为例, 将递归过程打印出来. 树为:
执行源代码, 递归过程为:
执行 plus( 5,0 )
执行 plus( 4,5 )
执行 plus( 11,9 )
执行 plus( 7,20 )
叶结点: 7 sum1= 27
执行 plus( 2,20 )
叶结点: 2 sum1= 22
执行 plus( 8,5 )
执行 plus( 13,13 )
叶结点: 13 sum1= 26
执行 plus( 4,13 )
执行 plus( 1,17 )
叶结点: 1 sum1= 18
来源: https://juejin.im/post/5c99c907e51d455a7e7734dc