leetcode

LeetCode 437. Path Sum III

Problem

LeetCode 437. Path Sum III

1. 题目简述

给出一棵二叉树和一个sum值，根节点为root，找出所有路path为sum的路径的数量，这里的path不一定要从根节点到叶子节点，但是一定要从父亲节点到孩子节点，不能回溯。例如：

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

2. 算法思路

DFS

此题难度为easy是我没想到的，其实感觉逻辑上还是有点难理解的，而且存在一种巧妙的HashMap的做法，作为解法2。

第一种解法。对于这个和之前最大的不同就是需要考虑不是从根节点出发的path了，对于某节点p来说我们需要计算的是包含p节点的以p为start出发的path；然后再加上从p的左右孩子出发的path，左子树和右子树分别计算。勉强算是前序遍历？完全取决于return的加法顺序。

第二种解法。逆向思维，第一种解法中考虑了从某节点p出发的path和为sum的路径；在这个基础上，我们是否可以换个思路，考虑了以某节点p结尾的path和为sum的路径。因此，对于任意一个节点p，我们需要计算的是以p为结尾的路径和为sum的path数，然后将其加和。

3. 解法

  1. 使用LinkedList保存当前路径，遍历后从currPath中删除当前节点，一定要删除！而且要注意，add到result里的时候，记得new一个对象，否则currPath会变。
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        return findPathSum(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum)
    }

    // 经过以root节点为start节点的path，和为sum的路径个数
    private int findPathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return (root.val == sum ? 1 : 0) + findPathSum(root.left, sum - root.val) + findPathSum(root.right, sum - root.val);
    }
}
  1. 使用HashMap来记录到某节点p之前的，从root节点到其中任意一个节点的路径之和，方法很巧妙，需要硬记。记得最后要删除当前这个currSum的记录。

class Solution {
    int count = 0;
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> preSumMap = new HashMap();
        preSumMap.put(0, 1);
        findPathSum(root, 0, sum, preSumMap);
        return count;
    }

    private void findPathSum(TreeNode root, int currSum, int target, Map<Integer, Integer> preSumMap) {
        if (root == null) {
            return;
        }

        currSum += root.val;

        if (preSumMap.containsKey(currSum - target)) {
            count += preSumMap.get(currSum - target);
        }

        preSumMap.put(currSum, preSumMap.containsKey(currSum) ?(preSumMap.get(currSum) + 1) : 1);

        findPathSum(root.left, currSum, target, preSumMap);
        findPathSum(root.right, currSum, target, preSumMap);

        preSumMap.put(currSum, preSumMap.get(currSum) - 1);
    }
}