二叉树 - 路径求和 I、II、III - 《计算机基础》

例题
- 路径总和 I">1.路径总和 I
  - 思路
- 路径总和 II">2.路径总和 II
  - 思路
- 路径总和 III">3.路径总和 III
  - 思路

例题

1.路径总和 I

给你二叉树的根节点root 和一个表示目标和的整数 targetSum 。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回true ；否则，返回 false 。
叶子节点是指没有子节点的节点。
示例： :::info 给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。 :::

思路

采用深度优先搜索遍历 DFS ，每经历过一个节点，目标值删除掉当前节点值。
当当前节点为叶子节点时，目标值如果等于当前节点值，则返回true，否则返回false

var hasPathSum = function(root, targetSum) {
    if (!root) return false;
    if (!root.left && !root.right) {
        return targetSum === root.val
    }
    return (
        hasPathSum(root.left, targetSum - root.val) ||
        hasPathSum(root.right, targetSum - root.val)
    )
};

2.路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
叶子节点是指没有子节点的节点。 :::info 给定如下二叉树，以及目标和 sum = 22.
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回: [
[5,4,11,2],
[5,8,4,5]
] :::

思路

本道题是在上述的 路径总和 I 的基础上去进行解答。
定义一个收集路径的数组arr，在每经历过一个节点的时候，将其加入到数组arr中。当遍历到叶子节点的时候，判断目标值是否与当前节点值相等，如果相等则浅拷贝后加入到结果数组res中，然后arr数组再次弹出当前节点值即可。

var pathSum = function(root, targetSum) {
    let res = []
    const dfs = function (root, arr, target) {
        if (!root) return;
        arr.push(root.val)
        if (target === root.val && !root.left && !root.right) {
            res.push(arr.slice())
        }
        root.left && dfs(root.left, arr, target - root.val)
        root.right && dfs(root.right, arr, target - root.val)
        arr.pop()
    }
    dfs(root, [], targetSum)
    return res
};

3.路径总和 III

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

思路

递归

统计统计三个值：

以 node 为起点，包含这个 node 本身加起来等于 sum 的路径数量之和。
以 node.left 为起点，等于 sum 的路径数量之和。
以 node.right 为起点，等于 sum 的路径数量之和。 ```javascript let pathSum = function (root, sum) { if (!root) return 0 return ( countSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum) ) }

let countSum = (node, sum) => { let count = 0 let dfs = (node, target) => { if (!node) return

// 这里拿到结果不能直接return 要继续向下考虑
// 比如下面的两个节点是 1, -1 那么它们相加得 0 也能得到一个路径
if (node.val === target) {
  count += 1
}
dfs(node.left, target - node.val)
dfs(node.right, target - node.val)

} dfs(node, sum) return count }


- **前缀和**
在上面的递归思路中，时间复杂度过于高，我们可以采用前缀和的思路。<br />具体思路可以借鉴[前缀和的运用，一步步优化](https://leetcode.cn/problems/subarray-sum-equals-k/solution/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y/)，讲得很好
```javascript
var pathSum = function(root, targetSum) {
     const prefix = new Map()
    //  初始化空路径
     prefix.set(0, 1)
     return dfs(root, prefix, targetSum, 0)
};
// 前缀和
const dfs = function(root, prefix, targetSum, curr) {
    if(!root) return 0
    let ret = 0
    curr += root.val
    ret = prefix.get(curr - targetSum) || 0
    prefix.set(curr, (prefix.get(curr) || 0) + 1)
    ret += dfs(root.left, prefix, targetSum, curr)
    ret += dfs(root.right, prefix, targetSum, curr)
    // 当前节点遍历调用后减一
    prefix.set(curr, (prefix.get(curr) || 0) - 1)
    return ret
}