-
Notifications
You must be signed in to change notification settings - Fork 1
/
112-Path-Sum.py
32 lines (30 loc) · 1013 Bytes
/
112-Path-Sum.py
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
# Definition for a binary tree node.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root is None:
return False
if root.left is None and root.right is None and root.val==sum:
return True
return self.hasPathSum(root.left,sum-root.val) or self.hasPathSum(root.right,sum-root.val)
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if root is None:
return False
self.flag=False
def dfs(node,acc):
if self.flag:
return
if node.left==None and node.right==None:
if acc+node.val==sum:
self.flag=True
if node.left:
dfs(node.left,acc+node.val)
if node.right:
dfs(node.right,acc+node.val)
dfs(root,0)
return self.flag