0437-路径总和 III

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 15:32:49 2023-09-13 15:32:49 Updated    

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

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

示例 1：

**输入：** root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
**输出：** 3
**解释：** 和等于 8 的路径有 3 条，如图所示。

示例 2：

**输入：** root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
**输出：** 3

提示:

  • 二叉树的节点个数的范围是 [0,1000]
  • -109 <= Node.val <= 109
  • -1000 <= targetSum <= 1000

方法一：深度优先搜索

思路与算法

我们首先想到的解法是穷举所有的可能，我们访问每一个节点 node，检测以 node 为起始节点且向下延深的路径有多少种。我们递归遍历每一个节点的所有可能的路径，然后将这些路径数目加起来即为返回结果。

  • 我们首先定义 rootSum}(p,\textit{val})$ 表示以节点 $p$ 为起点向下且满足路径总和为 $val$ 的路径数目。我们对二叉树上每个节点 $p$ 求出 rootSum}(p,\textit{targetSum})$，然后对这些路径数目求和即为返回结果。

  • 我们对节点 $p$ 求 rootSum}(p,\textit{targetSum})$ 时，以当前节点 $p$ 为目标路径的起点递归向下进行搜索。假设当前的节点 $p$ 的值为 val，我们对左子树和右子树进行递归搜索，对节点 $p$ 的左孩子节点 $p_{l 求出 rootSum}(p_{l},\textit{targetSum}-\textit{val})$，以及对右孩子节点 $p_{r 求出 rootSum}(p_{r},\textit{targetSum}-\textit{val})$。节点 $p$ 的 rootSum}(p,\textit{targetSum})$ 即等于 rootSum}(p_{l},\textit{targetSum}-\textit{val})$ 与 rootSum}(p_{r},\textit{targetSum}-\textit{val})$ 之和，同时我们还需要判断一下当前节点 $p$ 的值是否刚好等于 targetSum。

  • 我们采用递归遍历二叉树的每个节点 $p$，对节点 $p$ 求 rootSum}(p,\textit{val})$，然后将每个节点所有求的值进行相加求和返回。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int rootSum(TreeNode* root, long targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        if (root->val == targetSum) {
            ret++;
        } 

        ret += rootSum(root->left, targetSum - root->val);
        ret += rootSum(root->right, targetSum - root->val);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (!root) {
            return 0;
        }
        
        int ret = rootSum(root, targetSum);
        ret += pathSum(root->left, targetSum);
        ret += pathSum(root->right, targetSum);
        return ret;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = rootSum(root, targetSum);
        ret += pathSum(root.left, targetSum);
        ret += pathSum(root.right, targetSum);
        return ret;
    }

    public int rootSum(TreeNode root, int targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        } 

        ret += rootSum(root.left, targetSum - val);
        ret += rootSum(root.right, targetSum - val);
        return ret;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int PathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = RootSum(root, targetSum);
        ret += PathSum(root.left, targetSum);
        ret += PathSum(root.right, targetSum);
        return ret;
    }

    public int RootSum(TreeNode root, int targetSum) {
        int ret = 0;

        if (root == null) {
            return 0;
        }
        int val = root.val;
        if (val == targetSum) {
            ret++;
        } 

        ret += RootSum(root.left, targetSum - val);
        ret += RootSum(root.right, targetSum - val);
        return ret;
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        def rootSum(root, targetSum):
            if root is None:
                return 0

            ret = 0
            if root.val == targetSum:
                ret += 1

            ret += rootSum(root.left, targetSum - root.val)
            ret += rootSum(root.right, targetSum - root.val)
            return ret
        
        if root is None:
            return 0
            
        ret = rootSum(root, targetSum)
        ret += self.pathSum(root.left, targetSum)
        ret += self.pathSum(root.right, targetSum)
        return ret
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var pathSum = function(root, targetSum) {
    if (root == null) {
        return 0;
    }
    
    let ret = rootSum(root, targetSum);
    ret += pathSum(root.left, targetSum);
    ret += pathSum(root.right, targetSum);
    return ret;
};

const rootSum = (root, targetSum) => {
    let ret = 0;

    if (root == null) {
        return 0;
    }
    const val = root.val;
    if (val === targetSum) {
        ret++;
    } 

    ret += rootSum(root.left, targetSum - val);
    ret += rootSum(root.right, targetSum - val);
    return ret;
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func rootSum(root *TreeNode, targetSum int) (res int) {
    if root == nil {
        return
    }
    val := root.Val
    if val == targetSum {
        res++
    }
    res += rootSum(root.Left, targetSum-val)
    res += rootSum(root.Right, targetSum-val)
    return
}

func pathSum(root *TreeNode, targetSum int) int {
    if root == nil {
        return 0
    }
    res := rootSum(root, targetSum)
    res += pathSum(root.Left, targetSum)
    res += pathSum(root.Right, targetSum)
    return res
}

复杂度分析

  • 时间复杂度：$O(N^2)$，其中 $N$ 为该二叉树节点的个数。对于每一个节点，求以该节点为起点的路径数目时，则需要遍历以该节点为根节点的子树的所有节点，因此求该路径所花费的最大时间为 $O(N)$，我们会对每个节点都求一次以该节点为起点的路径数目，因此时间复杂度为 $O(N^{2})$。

  • 空间复杂度：$O(N)$，考虑到递归需要在栈上开辟空间。

方法二: 前缀和

思路与算法

我们仔细思考一下，解法一中应该存在许多重复计算。我们定义节点的前缀和为：由根结点到当前结点的路径上所有节点的和。我们利用先序遍历二叉树，记录下根节点 root 到当前节点 $p$ 的路径上除当前节点以外所有节点的前缀和，在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 $curr$ 减去 targetSum。

  • 对于空路径我们也需要保存预先处理一下，此时因为空路径不经过任何节点，因此它的前缀和为 $0$。

  • 假设根节点为 root，我们当前刚好访问节点 node，则此时从根节点 root 到节点 node 的路径（无重复节点）刚好为 root} \rightarrow p_1 \rightarrow p_2 \rightarrow \ldots \rightarrow p_k \rightarrow \textit{node，此时我们可以已经保存了节点 $p_1, p_2, p_3, \ldots, p_k$ 的前缀和，并且计算出了节点 node 的前缀和。

  • 假设当前从根节点 root 到节点 node 的前缀和为 curr，则此时我们在已保存的前缀和查找是否存在前缀和刚好等于 curr} - \textit{targetSum。假设从根节点 root 到节点 node 的路径中存在节点 $p_i$ 到根节点 root 的前缀和为 curr} - \textit{targetSum，则节点 $p_{i+1 到 node 的路径上所有节点的和一定为 targetSum。

  • 我们利用深度搜索遍历树，当我们退出当前节点时，我们需要及时更新已经保存的前缀和。

代码

[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    unordered_map<long long, int> prefix;

    int dfs(TreeNode *root, long long curr, int targetSum) {
        if (!root) {
            return 0;
        }

        int ret = 0;
        curr += root->val;
        if (prefix.count(curr - targetSum)) {
            ret = prefix[curr - targetSum];
        }

        prefix[curr]++;
        ret += dfs(root->left, curr, targetSum);
        ret += dfs(root->right, curr, targetSum);
        prefix[curr]--;

        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        prefix[0] = 1;
        return dfs(root, 0, targetSum);
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        Map<Long, Integer> prefix = new HashMap<Long, Integer>();
        prefix.put(0L, 1);
        return dfs(root, prefix, 0, targetSum);
    }

    public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;

        ret = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
        ret += dfs(root.left, prefix, curr, targetSum);
        ret += dfs(root.right, prefix, curr, targetSum);
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

        return ret;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int PathSum(TreeNode root, int targetSum) {
        Dictionary<long, int> prefix = new Dictionary<long, int>();
        prefix.Add(0, 1);
        return DFS(root, prefix, 0, targetSum);
    }

    public int DFS(TreeNode root, Dictionary<long, int> prefix, long curr, int targetSum) {
        if (root == null) {
            return 0;
        }

        int ret = 0;
        curr += root.val;

        prefix.TryGetValue(curr - targetSum, out ret);
        if (prefix.ContainsKey(curr)) {
            ++prefix[curr];
        } else {
            prefix.Add(curr, 1);
        }
        ret += DFS(root.left, prefix, curr, targetSum);
        ret += DFS(root.right, prefix, curr, targetSum);
        --prefix[curr];

        return ret;
    }
}
[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        prefix = collections.defaultdict(int)
        prefix[0] = 1

        def dfs(root, curr):
            if not root:
                return 0
            
            ret = 0
            curr += root.val
            ret += prefix[curr - targetSum]
            prefix[curr] += 1
            ret += dfs(root.left, curr)
            ret += dfs(root.right, curr)
            prefix[curr] -= 1

            return ret

        return dfs(root, 0)
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var pathSum = function(root, targetSum) {
    const prefix = new Map();
    prefix.set(0, 1);
    return dfs(root, prefix, 0, targetSum);
}

const dfs = (root, prefix, curr, targetSum) => {
    if (root == null) {
        return 0;
    }

    let ret = 0;
    curr += root.val;

    ret = prefix.get(curr - targetSum) || 0;
    prefix.set(curr, (prefix.get(curr) || 0) + 1);
    ret += dfs(root.left, prefix, curr, targetSum);
    ret += dfs(root.right, prefix, curr, targetSum);
    prefix.set(curr, (prefix.get(curr) || 0) - 1);

    return ret;
}
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func pathSum(root *TreeNode, targetSum int) (ans int) {
    preSum := map[int64]int{0: 1}
    var dfs func(*TreeNode, int64)
    dfs = func(node *TreeNode, curr int64) {
        if node == nil {
            return
        }
        curr += int64(node.Val)
        ans += preSum[curr-int64(targetSum)]
        preSum[curr]++
        dfs(node.Left, curr)
        dfs(node.Right, curr)
        preSum[curr]--
        return
    }
    dfs(root, 0)
    return
}

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$ 为二叉树中节点的个数。利用前缀和只需遍历一次二叉树即可。

  • 空间复杂度：$O(N)$。

 Comments
On this page
0437-路径总和 III