树路径和

Question

问题-

我的解决方案-

public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null || sum == 0){
            return false;
        }
        List<Integer> resultSet = new ArrayList<Integer>();
        Integer result = root.val;
        inorder(root, result, resultSet);
        return resultSet.contains(sum);
    }
    public void inorder(TreeNode root, Integer result, List<Integer> resultSet){
        if (root.left == null && root.right == null){
            resultSet.add(result);
        }
        if (root.left != null) {
            result += Integer.valueOf(root.left.val);
            inorder(root.left, result, resultSet);
        }
        if (root.right != null) {
            result += Integer.valueOf(root.right.val);
            inorder(root.right, result, resultSet);
        }

    }
}

输出-

输入：[1，-2，-3,1,3，-2，null，-1]3输出：应为真：假

我真的不知道我在这方面出了什么问题。我尝试玩int和整数类型选项的结果，但它不工作。请帮忙。

Answer 1

我看到的问题是result变量，因为一旦将left节点的值添加到result中，并使用left子树完成后，u将向结果添加right child的值，这是错误的，因为现在它具有left和right子值之和。

所以本质上，您是在添加inorder遍历中节点root之前的结果中所有节点的值。

你能试试这个吗

public void inorder(TreeNode root, Integer result, List<Integer> resultSet){
    if (root.left == null && root.right == null){
        resultSet.add(result);
    }
    if (root.left != null) {
        inorder(root.left, result+Integer.valueOf(root.left.val), resultSet);
    }
    if (root.right != null) {
        inorder(root.right, result+Integer.valueOf(root.right.val), resultSet);
    }
}

编辑：1

解决此问题的另一种简单方法是：不需要创建包含所有根到叶路径之和的数组。您只需不断递减所需的总和。

代码：

public boolean hasPathSum(TreeNode root, int sum) {
    if (root == null) {
        return false;
    } else {
        return hasPathSumHelper(root, sum);
    }

}

boolean hasPathSumHelper(TreeNode root, int sum) {
    if (root.left == null && root.right == null) {//if leaf node
        if (Integer.valueOf(root.val) == sum) { //if node value is equal to sum
            return true;
        } else {
            return false;
        }
    }
    if ((root.left != null) && (root.right != null)) {
        return (hasPathSumHelper(root.left, sum - Integer.valueOf(root.val)) || hasPathSumHelper(root.right, sum - Integer.valueOf(root.val)));
    }
    if (root.left != null) {
        return hasPathSumHelper(root.left, sum - Integer.valueOf(root.val));
    } else {
        return hasPathSumHelper(root.right, sum - Integer.valueOf(root.val));
    }
}