0437. 路径总和 III

题目地址(437. 路径总和 III)

https://leetcode-cn.com/problems/path-sum-iii/

题目描述

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

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

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

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

示例：

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

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

返回 3。和等于 8 的路径有:

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

前置知识

• hashmap

公司

• 阿里

• 腾讯

• 百度

• 字节

思路

这道题目是要我们求解出任何一个节点出发到子孙节点的路径中和为指定值。 注意这里，不一定是从根节点出发，也不一定在叶子节点结束。

一种简单的思路就是直接递归解决，空间复杂度 O(n) 时间复杂度介于 O(nlogn) 和 O(n^2)， 具体代码：

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
// the number of the paths starting from self
function helper(root, sum) {
  if (root === null) return 0;
  const l = helper(root.left, sum - root.val);
  const r = helper(root.right, sum - root.val);

  return l + r + (root.val === sum ? 1 : 0);
}
/**
 * @param {TreeNode} root
 * @param {number} sum
 * @return {number}
 */
var pathSum = function (root, sum) {
  // 空间复杂度O(n) 时间复杂度介于O(nlogn) 和 O(n^2)
  // tag: dfs tree
  if (root === null) return 0;
  // the number of the paths starting from self
  const self = helper(root, sum);
  // we don't know the answer, so we just pass it down
  const l = pathSum(root.left, sum);
  // we don't know the answer, so we just pass it down
  const r = pathSum(root.right, sum);

  return self + l + r;
};

但是还有一种空间复杂度更加优秀的算法，利用 hashmap 来避免重复计算，时间复杂度和空间复杂度都是 O(n)。 这种思路是subarray-sum-equals-k的升级版本，如果那道题目你可以 O(n)解决，这道题目难度就不会很大， 只是将数组换成了二叉树。关于具体的思路可以看这道题目

这里有一个不一样的地方，这里我说明一下，就是为什么要有hashmap[acc] = hashmap[acc] - 1;， 原因很简单，就是我们 DFS 的时候，从底部往上回溯的时候，map 的值应该也回溯。如果你对回溯法比较熟悉的话， 应该很容易理解，如果不熟悉可以参考这道题目， 这道题目就是通过tempList.pop()来完成的。

另外我画了一个图，相信看完你就明白了。

当我们执行到底部的时候：

437.path-sum-iii

接着往上回溯：

437.path-sum-iii-2

很容易看出，我们的 hashmap 不应该有第一张图的那个记录了，因此需要减去。

具体实现见下方代码区。

关键点解析

• 通过 hashmap，以空间换时间

• 对于这种连续的元素求和问题，有一个共同的思路，可以参考这道题目

代码

• 语言支持：JS, Python

JS code:

/*
 * @lc app=leetcode id=437 lang=javascript
 *
 * [437] Path Sum III
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
function helper(root, acc, target, hashmap) {
  // see also : https://leetcode.com/problems/subarray-sum-equals-k/

  if (root === null) return 0;
  let count = 0;
  acc += root.val;
  if (acc === target) count++;
  if (hashmap[acc - target] !== void 0) {
    count += hashmap[acc - target];
  }
  if (hashmap[acc] === void 0) {
    hashmap[acc] = 1;
  } else {
    hashmap[acc] += 1;
  }
  const res =
    count +
    helper(root.left, acc, target, hashmap) +
    helper(root.right, acc, target, hashmap);

  // 这里要注意别忘记了
  hashmap[acc] = hashmap[acc] - 1;

  return res;
}

var pathSum = function (root, sum) {
  const hashmap = {};
  return helper(root, 0, sum, hashmap);
};

Python Code:

import collections
'''
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
'''
class Solution:
    def helper(self,root,acc,target,hashmap):
        if not root:
            return 0
        count=0
        acc+=root.val
        if acc==target:
            count+=1
        if acc-target in hashmap:
            count+=hashmap[acc-target]
        hashmap[acc]+=1
        if root.left:
            count+=self.helper(root.left,acc,target,hashmap)
        if root.right:
            count+=self.helper(root.right,acc,target,hashmap)
        hashmap[acc]-=1
        return count
    
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        hashmap=collections.defaultdict(lambda:0)
        return self.helper(root,0,targetSum,hashmap)

复杂度分析

• 时间复杂度：$O(N)$

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

更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。