Path Sum II

系统管理员 2021-12-17 10:33 219阅读 0赞

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\] \]  
  
求二叉树从根到叶子结点，结点和等于sum的所有路径。很有意思的一道题目，解法是DFS，深搜。判断根到每个叶子结点的路径和是否等于sum。具体解法有结合backtracking回溯的或者不结合两种，回溯代码如下：

class Solution(object):
        def pathSum(self, root, sum):
            """
            :type root: TreeNode
            :type sum: int
            :rtype: List[List[int]]
            """
            if not root:
                return []
            res = []   #返回结果
            path = []  #当前路径
            self.helper(root, path, res, sum)
            return res
            
        def helper(self, node, path, res, sum):
            if not node:
                return 
            path.append(node.val)
            if not node.left and not node.right:
                if sum == node.val:
                    res.append(path+[])
            self.helper(node.left,path,res,sum-node.val)
            self.helper(node.right,path,res,sum-node.val)
            path.pop() #如果到达叶子结点，弹出该结点的值，回到上一步的路径。

可以看到回溯方法，函数中共用path, path作为引用使用，处理完一个叶子结点，就进行弹出处理，方便后续别的路径的检查。遍历完每个结点，时间复杂度为O(n),空间复杂度为栈的高度O(logn)。

非回溯方法：

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

非回溯方法由于每个函数调用内部都做了path = path + \[node.val\]的操作，函数内部的path不同于传入函数内部的path，所以函数内部不能共享path,空间复杂度比较高，依然是遍历一次每个结点，时间复杂度O(n)。

转载于:https://www.cnblogs.com/sherylwang/p/5466990.html