LeetCode--112--路径总和

问题描述：

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / 
            4   8
           /   / 
          11  13  4
         /        
        7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

错误：

 1 class Solution(object):
 2     def hasPathSum(self, root, sum):
 3         """
 4         :type root: TreeNode
 5         :type sum: int
 6         :rtype: bool
 7         """
 8         def preOrder(self,root,sum,temp_sum): 
 9             if self.flag:
10                 return self.flag
11             elif root and not self.flag:
12                 temp_sum += root.val 
13                 if not root.left and not root.right:          
14                     if sum == temp_sum:
15                         self.flag = True  
16                         return 
17                     else :
18                         temp_sum -= root.val
19                         self.flag = False
20             if root == None:
21                 return
22                 preOrder(self,root.left,sum,temp_sum)
23                 preOrder(self,root.right,sum,temp_sum)
24         self.flag = False
25         return preOrder(self,root,sum,0)

改正：

 1 class Solution(object):
 2     def hasPathSum(self, root, sum):
 3         """
 4         :type root: TreeNode
 5         :type sum: int
 6         :rtype: bool
 7         """
 8         self.flag = False
 9         def preOrder(self,root,sum,temp_sum): 
10             if not self.flag:
11                 if root:
12                     temp_sum += root.val 
13                     if root.left or root.right:                       
14                         preOrder(self,root.left,sum,temp_sum)
15                         preOrder(self,root.right,sum,temp_sum)
16                     else:
17                         if sum == temp_sum:
18                             self.flag = True
19                         else:
20                             temp_sum -= root.val
21         if root:
22             preOrder(self,root,sum,0)
23         return self.flag

参考：

 1 class Solution(object):
 2     def hasPathSum(self, root, sum):
 3         """
 4         :type root: TreeNode
 5         :type sum: int
 6         :rtype: bool
 7         """
 8         self.flag = False
 9         def dfs(node,sumNow = 0,target = sum):
10             if not self.flag:
11                 if node:
12                     sumNow += node.val
13                     if node.left or node.right:
14                         dfs(node.left, sumNow, target)
15                         dfs(node.right, sumNow, target)
16                     else:
17                         if sumNow == target:
18                             self.flag = True
19         if root:
20             dfs(root)
21         return self.flag

官方：

 1 class Solution(object):
 2     def hasPathSum(self, root, sum):
 3         """
 4         :type root: TreeNode
 5         :type sum: int
 6         :rtype: bool
 7         """
 8         if root is None:
 9             return False
10         if root.left is None and root.right is None:
11             return root.val == sum
12         if root.left == None:
13             return self.hasPathSum(root.right,sum - root.val)
14         if root.right == None:
15             return self.hasPathSum(root.left,sum - root.val)
16         return self.hasPathSum(root.left,sum - root.val) or self.hasPathSum(root.right,sum - root.val)

2018-09-10 20:54:47