Path Sum II

题目

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:

Given the below binary tree and

sum = 22

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

return

[
   [5,4,11,2],
   [5,8,4,5]
]

思路分析

这道题通过分析题意可以很快定位到用DFS的第二类解法来实现，不同点是这个是一个binary tree的题，所以每一个根结点只调用左子树和右子树两次递归，通过在递归函数的定义中加入path和result的方法来实现

class Solution(object):
    def pathSum(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        def dfs(root, sum, path, result):
            if root == None: return
            if not root.left and not root.right:
                if sum == root.val: result.append(path+[root.val])
            if root.left: dfs(root.left, sum-root.val, path+[root.val], result)
            if root.right: dfs(root.right, sum-root.val, path+[root.val], result)
        result = []
        dfs(root, sum, [], result)
        return result

复杂度分析

这道题的复杂度可以通过多少次递归来得到，如果这个树有N个结点那个递归函数被调用了N次，而每次递归函数的处理复杂度是O(1)，所以可以得出这道题的实现时间复杂度为O(N)