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

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

return true, as there exist a root-to-leaf path5->4->11->2which sum is 22.

思路分析

这道题很明显是DFS的第一类问题，寻找是不是有解的问题。这道题直接带入是不是有解的DFS模版很容易实现。但是我在做这道题的时候受到了DFS第二类问题的影响，因为大部分的DFS问题是第二类问题（寻找所有解）。在两种方法都可以实现，但是通过这道题我们可以分析一下这两种实现方式的区别。

• 使用DFS第一类问题实现的模版（boolean solve(Node n)）

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        if root == None: return False
        if root.left == None and root.right == None:
            if sum == root.val: return True
            else: return False
        if root.left and self.hasPathSum(root.left, sum-root.val): return True
        if root.right and self.hasPathSum(root.right, sum-root.val): return True
        return False

在这里先对这个代码分析一下，这个代码基本就是DFS第一类问题的模版。这里有一个问题需要问一下，为什么最后一行return false不是在每一个if语句后，而是所有的if... return true之后呢？这是因为要一直判断一个path上的每一个结点（这个结点包含所有的分支，在这里就是左子树和右子树），如果有一个path上的所有结点都是True，则return True，否则return False

• 使用DFS第二类问题实现的模版

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        def dfs(root, sum, result):
            if root == None: return False
            if root.left == None and root.right == None:
                if sum == root.val: 
                    result.append(True)
                    return
            if root.left:
                dfs(root.left, sum-root.val, result)
            if root.right:
                dfs(root.right, sum-root.val, result)
        result = []
        dfs(root, sum, result)
        return True in result

这个实现方法就是把True值放在一个数组里面，最后判断数组中是不是包含True。那么问题来了，为什么不把True直接付给一个boolean型的变量result呢？就是说把result.append(True)变成result=True，这样是不行的，因为boolean型的变量传递到函数dfs后函数内部result的变化是不会改变dfs函数外的result值的，所以这种情况下reuslt的值会一直是False。

那么有没有办法用一个全局变量来实现呢，也就是说DFS函数内部对result的改变也会相应地改变DFS外面的result的值

class Solution(object):
    def hasPathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: bool
        """
        def dfs(root, sum):
            if root == None: return False
            if root.left == None and root.right == None:
                if sum == root.val: 
                    self.result = True
                    return
            if root.left:
                dfs(root.left, sum-root.val)
            if root.right:
                dfs(root.right, sum-root.val)
        self.result = False       <<<<< Global parameter self.result can be changed inside DFS function
        dfs(root, sum)
        return self.result