Skip to content

Latest commit

 

History

History
104 lines (70 loc) · 3.22 KB

0437-path-sum-iii.adoc

File metadata and controls

104 lines (70 loc) · 3.22 KB
Raw

437. Path Sum III

{leetcode}/problems/path-sum-iii/[LeetCode - Path Sum III^]

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

{image_attr}

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:
root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

思路分析

link:{sourcedir}/_0437_PathSumIII.java[role=include]
错误提交
link:{sourcedir}/_0437_PathSumIII_2.java[role=include]
link:{sourcedir}/_0437_PathSumIII_21.java[role=include]

前缀和解法

  1. 前缀和定义：一个节点的前缀和就是该节点到根之间的路径和。

  2. 前缀和对于本题的作用：两节点间的路径和=两节点的前缀和之差

  3. Map 存的是什么: Map 的 key 是前缀和， value 是该前缀和在已遍历的节点中的出现频率

  4. 恢复状态的意义：

    1. 题目要求：路径方向必须是向下的（只能从父节点到子节点）

    2. 所以当我们讨论两个节点的前缀和差值时，有一个前提：一个节点必须是另一个节点的祖先节点。

    3. 也就是说，当我们把一个节点的前缀和信息更新到hashMap里时，它应当只对其子节点有效。

    4. 所以我们应该：在遍历完一个节点的所有子节点后，将其从 Map 中减去它的频率。

{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr}
{image_attr} 
link:{sourcedir}/_0437_PathSumIII_22.java[role=include]

思考题

感觉目前的解法还是有些繁琐。效仿 java解法 时间100% 空间93% - 路径总和 III，设计一个更加高效的实现。