Java描述 LeetCode，513. Path Sum路径总和

Java描述 LeetCode，513. Path Sum路径总和

大家好，我是河海哥，专注于后端，如果可以的话，想做一名code designer而不是普通的coder，一起见证河海哥的成长，您的评论与赞是我的最大动力，如有错误还请不吝赐教，万分感谢。一起支持原创吧！纯手打有笔误还望谅解。

1-1: description

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false
Explanation: There two root-to-leaf paths in the tree:
(1 --> 2): The sum is 3.
(1 --> 3): The sum is 4.
There is no root-to-leaf path with sum = 5.

Example 3:

Input: root = [], targetSum = 0
Output: false
Explanation: Since the tree is empty, there are no root-to-leaf paths.

Constraints:

The number of nodes in the tree is in the range [0, 5000].
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum

1-2: recursion

☘️这里主要是两个问题，遍历的时候要关注是不是到达叶子节点，并且到达叶子节点的时候所经过的路径之和是不是为指定的目标值。到达叶子节点好办，只需要判断左右是不是空就可以了，经过的路径之和可以用一个path来保存所有经过的节点的和。

那么我一开始的想法是，对于一个节点一共有四种情况

• 左null，右null
• 左非空，右空
• 左空，右非空
• 左右均是非空

☘️于是给出了下面的代码，因为我们多用了一个path参数，所以要重新写一个递归函数。

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    return pathSum(root, 0, targetSum);
}

public boolean pathSum(TreeNode root, int path, int targetSum) {
    if (root.left == null && root.right != null) {
        path += root.val;
        return pathSum(root.right, path, targetSum);
    }
    if (root.left != null && root.right == null) {
        path += root.val;
        return pathSum(root.left, path, targetSum);
    }
    if (root.left == null && root.right == null) {
        path += root.val;
        return path == targetSum;
    }
    if (root.left != null && root.right != null) {
        path += root.val;
        return pathSum(root.left, path, targetSum) || pathSum(root.right, path, targetSum);
    }
    return false;
}

☘️是的，这一串很繁琐的代码，但是却很好地说明了那几种情况。那么接下来我们就开始简化它，灵感就在与左右都非空的时候，左右子树只要有一条路能满足条件，就说明整棵树存在这样的路径。那么，当左右有一个为空的情况的时候，我们选择往非空的节点继续递归，试想一下，如果对于空的节点返回false，非空节点继续递归，取一个|| *** 作，不也能达到效果吗？所以上面列举的后三种情况是可以合并起来的。于是有了如下的代码。

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    return pathSum2(root, 0, targetSum);
}
    
public boolean pathSum2(TreeNode root, int path, int targetSum) {
    if (root == null) {
        return false;
    }
    path += root.val;
    if (root.left == null && root.right == null) {
        return path == targetSum;
    }
    return pathSum(root.left, path, targetSum) || pathSum(root.right, path, targetSum);
}

☘️但是再想一下，我这里用了一个path来记录和了，能不能不用path呢？我自己没想明白，看了答案，我一直都是想的把节点的和加起来，却没想到取一个就减去一个节点的值，到了叶子节点再把剩余的值和叶子节点的值对比起来，不就好了？

public boolean pathSum3(TreeNode root, int path, int targetSum) {
    if (root == null) {
        return false;
    }
    path += root.val;
    if (root.left == null && root.right == null) {
        return path == targetSum;
    }
    return pathSum(root.left, path, targetSum) || pathSum(root.right, path, targetSum);
}

1-3: iteration

迭代还是比较好写的，这里就不写了，自己对递归不太会。