LeetCode 112. Path Sum

题目

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
```
return true, as there exist a root-to-leaf path `5->4->11->2` which sum is 22.
## 分析
找出二叉树中是否存在路径上所有节点的和等于给定值的路径
## 代码

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 hasPathSum(self, root, sum):
“””
:type root: TreeNode
:type sum: int
:rtype: bool
“””
if not root:
return False
if not root.left and not root.right and root.val == sum:
return True
sum -= root.val
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
```

点评

常规的递归深度优先搜索,每次递归的时候传递子树根节点和剩余的目标值,返回的是该子树是否符合条件,递归的终止条件是节点为 None,或者 没有子树了,而且该单节点树符合条件