437. 路径总和 III

437. 路径总和 III - 力扣（LeetCode）

class Solution {
  int TreeTarget(TreeNode *TN, int64_t Target) {
    if (!TN)
      return 0;
    
    int Num = 0;
    if (TN->val == Target)
      ++Num;
    
    Num += TreeTarget(TN->left, Target - TN->val);
    Num += TreeTarget(TN->right, Target - TN->val);
    return Num;
  }
public:
  int pathSum(TreeNode* root, int targetSum) {
    if (!root)
      return 0;

    int ret = TreeTarget(root, targetSum);
    ret += pathSum(root->left, targetSum);
    ret += pathSum(root->right, targetSum);
    return ret;
  }
};

不要把思路局限在「树只能一次遍历」上面。事实上你完全可以在遍历的过程中继续 dispatch，这就是所谓的深度优先搜索。

前缀和解法二刷的时候再看看。

二刷

class Solution {
  int Find(TreeNode *Root, int64_t Target) {
    if (!Root)
      return 0;

    int Left = Find(Root->left, Target - Root->val);
    int Right = Find(Root->right, Target - Root->val);
    return (Target == Root->val) + Left + Right;
  }
public:
  int pathSum(TreeNode* root, int targetSum) {
    if (!root)
      return 0;

    int Left = pathSum(root->left, targetSum);
    int Right = pathSum(root->right, targetSum);
    int This = Find(root, targetSum);
    return This + Left + Right;
  }
};

没什么好说的。优化的思路也非常明确：递归是无状态的，我们可以记录前缀和，来避免重复计算。

要注意的是，不要望文生义：前缀和不一定非得用数组存！你这是个树，用数组能存什么东西。用 unordered_map 完全是可以的。

class Solution {
  // Empty path is also a path. And it has a sum of zero.
  std::unordered_map<int64_t, int> PrefixCount_{{0, 1}};

  int Find(TreeNode *Root, int64_t Sum, int TargetSum) {
    if (!Root)
      return 0;

    int Count = 0;
    Sum += Root->val;
    // Keep in mind that we only have sums of every path originiated from the
    // ABSOLUTE root! So the only way we can achieve TargetSum is by subtracting
    // Prefix from current Sum. In this way, we get a partial path we want.
    // i.e. TargetSum == Sum - Prefix => Prefix == Sum - TargetSum.
    if (auto It = PrefixCount_.find(Sum - TargetSum); It != PrefixCount_.end())
      Count += *It;

    ++PrefixCount_[Sum];
    Count += Find(Root->left, Sum, TargetSum);
    Count += Find(Root->right, Sum, TargetSum);
    // Retract the count of Sum.
    --PrefixCount_[Sum];

    return Count;
  }

public:
  int pathSum(TreeNode* root, int targetSum) {
    if (!root)
      return 0;
    return Find(root, 0, targetSum);
  }
};

但是这个前缀和说实话，也有点绕人在里面的……我们需要注意的是，前缀 Prefix 以及前缀和 Sum 都始终是从绝对的根出发，走到当前节点的。所以我们得到 TargetSum 的方式，就只能是

$$ \text{Sum} - \text{Prefix} =\text{TargetSum} $$

从而我们可以移项得到

$$ \text{Prefix} = \text{Sum} - \text{TargetSum} $$

这就是我们在 PrefixCount_ 里要找到的东西。这个确实不好理解，如果不理解的话那就只能多背了。图类的题目也得去做一下。

此外，这题与其说是前序遍历，倒不如说是 DFS。从前缀和方法当中，你可以看到 DFS 非常经典的回溯；而递归方法的 Target，事实上也是 DFS 的「剩余步数」。

三刷

class Solution {
  // The int64_t is so annoying...
  unordered_map<int64_t, int> PrefixFreq_{{0, 1}};
  int DFS(TreeNode *TN, int64_t Sum, int Target) {
    if (!TN)
      return 0;

    // This function counts paths STARTING FROM TN with a sum of Target.
    int Count = 0;
    Sum += TN->val;
    // Firstly, check myself.
    if (auto It = PrefixFreq_.find(Sum - Target); It != PrefixFreq_.end())
      Count += It->second;

    // This is in fact a backtracking algorithm.
    ++PrefixFreq_[Sum];
    Count += DFS(TN->left, Sum, Target);
    Count += DFS(TN->right, Sum, Target);
    --PrefixFreq_[Sum];
    return Count;
  }
public:
  int pathSum(TreeNode* root, int targetSum) {
    return DFS(root, 0, targetSum);
  }
};

DFS 的好处就在于可以任意回溯，而不用担心之前走过的路径会不会对后面将要走的路径造成影响——比如说这题可能会想「之前存的前缀和不在当前路径上怎么办」，但其实压根不用担心，回溯就是了。

继续深入理解一下这个算法，会发现其实我们做的事情和不经过前缀和优化的递归解法是基本一样的，也就是我们仍然是针对从当前的根延伸出来的路径进行 DFS。唯一的区别就在于前缀和的 $\mathrm O(1)$ 访问让我们能够快速搜索。

此外注意这个恶心的 int64_t。你要改的话就得连着 Sum 参数和哈希表的键类型一起改，不然会出问题。

四刷

class Solution {
  unordered_map<int64_t, int> PrefixFreq_{{0, 1}};

  int DFS(TreeNode *TN, int64_t Sum, int Target) {
    if (!TN)
      return 0;

    Sum += TN->val;
    int Count = 0;
    if (auto It = PrefixFreq_.find(Sum - Target); It != PrefixFreq_.end())
      Count += It->second;

    ++PrefixFreq_[Sum];
    Count += DFS(TN->left, Sum, Target);
    Count += DFS(TN->right, Sum, Target);
    --PrefixFreq_[Sum];

    return Count;
  }
public:
  int pathSum(TreeNode* root, int targetSum) {
    return DFS(root, 0, targetSum);
  }
};

已经能背下来了。

五刷

class Solution {
  unordered_map<int64_t, int> PrefixFreq_{{0, 1}};
  int64_t Prefix_{};

public:
  int pathSum(TreeNode* root, int targetSum) {
    if (!root)
      return 0;

    Prefix_ += root->val;
    int Count = PrefixFreq_[Prefix_ - targetSum];

    ++PrefixFreq_[Prefix_];
	// Count += pathSum(root->left, targetSum - root->val);
    Count += pathSum(root->left, targetSum);
    Count += pathSum(root->right, targetSum);
    --PrefixFreq_[Prefix_];
    Prefix_ -= root->val;
    return Count;
  }
};

应该已经是究极简化版了。注意这里的直觉其实非常简单，就是前缀和相减，所以在传递targetSum的时候不用搞什么targetSum - root->val，这样反而会把事情搞复杂，破坏思路。