PeterQwQ
0%

Leetcode 437 路径总和 III

发表于

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。 路径不需要从根节点开始，也不需要在叶节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

首先用深度优先搜索遍历整个二叉树，将每个节点的父节点保存在字典中。然后遍历字典，对于每个节点，向上遍历到根节点，计算路径和，如果等于目标值，则计数器加一。

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
29
30
31
32
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        ans, parents = 0, {root: None}

        def dfs(node):
            if not node:
                return

            if node.left: parents[node.left] = node
            if node.right: parents[node.right] = node

            dfs(node.left)
            dfs(node.right)
        
        dfs(root)

        for node, parent in parents.items():
            cur_sum = 0
            while node:
                cur_sum += node.val
                if cur_sum == targetSum:
                    ans += 1

                node = parents[node]

        return ans