leetcode 437. 路径总和 III

[xxleyi]

题：

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

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

二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。

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

---

解：

惭愧，自己最初并没有独立做出来。在 leetcode.com 上看到一个讲解非常清晰的帖子。当时看懂之后，默写了一遍提交。现在使用「循环不变量」的视角下整理题解。

原帖：Python step-by-step walk through. Easy to understand. Two solutions comparison. : ) - LeetCode Discuss)

「循环不变量」视角下的代码，逻辑几乎没变，但着重强调「循环不变量」。

var pathSum = function(root, sum) {
  // initialize count to save result
  let count = 0
  // initialize loop invariant related variable: prefixSumMap for current node
  // with root node, we have {0: 1}
  let prefixSumMap = {0: 1}

  // initialize loop invariant related variable: prefixSum
  function loop(node = root, prefixSum = 0) {
    // check if we should return
    if (node == null) return

    // update prefixSum for current node
    prefixSum += node.val
    
    // update count
    count += (prefixSumMap[prefixSum - sum] || 0)
    // update loop invariant related variable prefixSumMap for node.left and node.right
    prefixSumMap[prefixSum] = (prefixSumMap[prefixSum] || 0) + 1

    // continue loop
    loop(node.left, prefixSum)
    loop(node.right, prefixSum)

    // when we finish to loop node.left and node.right
    // update loop invariant related variable prefixSumMap
    // because the prefixSum of current node is no longer needed
    prefixSumMap[prefixSum] -= 1
  }

  loop()

  // termination: count is the answer
  // and prefixSumMap (where value is not zero) should be {0: 1} again
  for (let [k, v] of Object.entries(prefixSumMap)) {
    if (v) console.assert(k == 0 && v == 1)
  }

  return count
}