路径总和III

Leetcode Link: 437. 路径总和 III - 力扣（LeetCode） (leetcode-cn.com)

题目

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

解法一

思路：（自己的思路）双重递归，一个笨方法 首先复习路径总和II，其使用的一重递归，在这里，双重递归就是对每一个节点，都进行当前节点到叶子节点进行遍历，走一遍路径总和II 的过程。

本题和路径总和II 的区别在于，这里不限制叶子节点，也就是说递归退出的条件需要改变

题解：

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        # 结果数量
        self.res = 0
        self.targetSum = targetSum
        # 一重递归：遍历每个节点
        self.recur1(root)
        return self.res
 
    def recur1(self, root):      
        if not root:
             return
 
        # 二重递归，每个节点都要重复一遍[[路径总和II]]
        self.recur2(root, self.targetSum)
    
        self.recur1(root.left)
        self.recur1(root.right)
 
    def recur2(self, node, tar):
        if not node:
            return
        # 注意这里的递归停止条件不限于叶子节点
        # 不在这里返回，有可能其孩子连着的两个正负数，那样不也是一个正确的路径嘛(II在这里返回了，因为是叶子节点了已经)
        if node.val == tar:
            self.res += 1
        if node.left: self.recur2(node.left, tar-node.val)
        if node.right: self.recur2(node.right, tar-node.val)

解法二

思路：

要讨论任意节点开始，到任意子节点的路径的和是否等于目标和，所以最好的办法就是记录这条路径的前缀和，并且及时维护，然后遍历是否有相等的来统计个数即可。

题解：

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        pre_sum = [0]
        res = 0
        def dfs(node):
            nonlocal res, targetSum
            if not node:
                return 
			# 两个注意
			# 1. 不能和自己比较，即要先遍历再 append
			# 2. 必须要包含第一位0来比较，即不能 for val in pre_sum[1:]，不知道为什么。
            cur_sum = pre_sum[-1]+node.val
            for val in pre_sum:
                if cur_sum - val == targetSum:
                    res+=1
            pre_sum.append(cur_sum)
            
            dfs(node.left)
            dfs(node.right)
            pre_sum.pop()
            return
        dfs(root)
        return res

两个注意

1. 不能和自己比较，即要先遍历再 append
2. 必须要包含第一位0来比较，即不能 for val in pre_sum[1:]，不知道为什么。我开始用0来占位，为了求当前位置的pre_sum好求。

解法三

review 的时候想到的解法，有点慢（比第一个慢十倍）

思路 用一个 path 维护当前节点之前的所有节点，需要及时 pop ()

1. 每次第一次访问一个节点，把该节点添加到 path
2. 遍历path,计算path[i:]的和，即计算每一位到最后一位的和，等于target的时候res++

题解

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        path = []
        res = 0
        def dfs(node):
            nonlocal targetSum, res
            if not node:
                return 
            
            path.append(node.val)
            for i in range(len(path)):
                if sum(path[i:]) == targetSum:
                    res += 1
            
            dfs(node.left)
            dfs(node.right)
 
            path.pop()
            return 
        
        dfs(root)
        return res

启发和联系