二叉树的路径和

问题描述

给定一个二叉树和一个整数sum，求二叉树中的一条连续的路径，使该路径上结点的和等于sum。

解决思路

这题和前面的一个题“和等于K的子数组”非常相似，因为他们都是采用哈希表来存储数据，然后通过间接的方法求得一段连续的值的和。

思路如下：

因为所求的结果是一段连续的路径，因此可以通过求差值的方法来判断该路径是否符合要求。因此，在先序遍历二叉树的时候，记录下每个路径的和出现的次数，这样，当我们处于某条路径时，如果该路径的和减去sum的值再哈希表中，说明我们曾经走过一条路径，该路径的和等于上述差值，而当前路径和该路径之间的路径就是一个解，通过这种方法就能在线性时间内找到所要求的答案。

public int pathSum(TreeNode root, int sum) {
    HashMap<Integer, Integer> preSum = new HashMap();
    preSum.put(0,1);
    return helper(root, 0, sum, preSum);
}

public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
    if (root == null) {
        return 0;
    }
    
    currSum += root.val;
    int res = preSum.getOrDefault(currSum - target, 0);
    preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);
    
    res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);
    preSum.put(currSum, preSum.get(currSum) - 1);
    return res;
}

总结

哈希表的功能和数组很相似，能够很快地查找到一些我们曾经求得的有用的值，这样，如果答案能够通过当前的值和旧值间接求出，那么哈希表能够发挥很大的作用。