LeetCode算法题-Path Sum III（Java实现）

这是悦乐书的第227次更新

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第94题（顺位题号是437）。您将获得一个二叉树，其中每个节点都包含一个整数值。找到与给定值相加的路径数。路径不需要在根或叶子处开始或结束，但必须向下（仅从父节点行进到子节点）。树的节点数不超过1,000个，值范围为-1,000,000到1,000,000。例如：

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

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

使用深度优先算法（DFS），因为题目说可以在任意节点开始，可以在任意节点结束,因此在开始位置有两个选择：从根节点开始；从根节点的子节点开始。而从根节点的子节点开始，此子问题和问题本身性质一样，需要调用自身。而从根节点开始，则需要调用另外一个方法，此方法同样是两个参数，当前节点和sum。

定义一个记数变量，记录可能的路径数。如果当前节点为null，返回0。如果当前节点值和sum相等，记数加1，同时对于当前节点的左节点、右节点继续调用此方法，而第二个参数sum，则需要减掉当前节点的值。

public int pathSum(TreeNode root, int sum) {
    if (root == null) {
        return 0;
    }
    return findPath(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

public int findPath(TreeNode root, int sum) {
    int result = 0;
    if (root == null) {
        return result;
    }
    if (sum == root.val) {
         result++;
    }
    result += findPath(root.left, sum-root.val);
    result += findPath(root.right, sum-root.val);
    return result;
}

03 第二种解法

此解法来自讨论区。对于树中的每个父节点，我们有两个选择：

1.将它包括在达到总和的路径中。

2.不要将其包含在达到总和的路径中。

对于树中的每个子节点，我们有2个选择：

1.取走父节点留给你的东西。

2.从自己开始形成路径。

传送门：https://leetcode.com/problems/path-sum-iii/discuss/91996/Easy-to-understand-Java-solution-with-comment.

int target;
Set<TreeNode> visited;
public int pathSum2(TreeNode root, int sum) {
    target = sum;
    //to store the nodes that have already tried to start path by themselves.
    visited = new HashSet<TreeNode>();  
    return pathSumHelper(root, sum, false);
}

public int pathSumHelper(TreeNode root, int sum, boolean hasParent) {
    if(root == null) return 0;
    //the hasParent flag is used to handle the case when parent path sum is 0.
    //in this case we still want to explore the current node.
    if (sum == target && visited.contains(root) && !hasParent) {
        return 0;
    }
    if (sum == target && !hasParent) {
        visited.add(root);
    }
    int count = (root.val == sum) ? 1 : 0;
    count += pathSumHelper(root.left, sum - root.val, true);
    count += pathSumHelper(root.right, sum - root.val, true);
    count += pathSumHelper(root.left, target , false);
    count += pathSumHelper(root.right, target, false);
    return count;
}

04 第三种解法

此解法同样来自讨论区，使用HashMap来操作。

传送门：https://leetcode.com/problems/path-sum-iii/discuss/91878/17-ms-O(n)-java-Prefix-sum-method

public int pathSum3(TreeNode root, int sum) {
    Map<Integer, Integer> map = new HashMap<>();
    //Default sum = 0 has one count
    map.put(0, 1);  
    return backtrack(root, 0, sum, map); 
}

public int backtrack(TreeNode root, int sum, int target, Map<Integer, Integer> map){
    if (root == null) {
        return 0;
    }
    sum += root.val;
    //See if there is a subarray sum equals to target
    int res = map.getOrDefault(sum - target, 0);    
    map.put(sum, map.getOrDefault(sum, 0)+1);
    //Extend to left and right child
    res += backtrack(root.left, sum, target, map);
    res += backtrack(root.right, sum, target, map);
    //Remove the current node so it won't affect other path
    map.put(sum, map.get(sum)-1);   
    return res;
}

05 小结

算法专题目前已连续日更超过两个月，算法题文章94+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。

以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！