问题描述：

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

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

示例: 

给定如下二叉树，以及目标和 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.flag11             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.val19                         self.flag = False20             if root == None:21                 return22                 preOrder(self,root.left,sum,temp_sum)23                 preOrder(self,root.right,sum,temp_sum)24         self.flag = False25         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 = True19                         else:20                             temp_sum -= root.val21         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.val13                     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 = True19         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 False10         if root.left is None and root.right is None:11             return root.val == sum12         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