树-路径总和

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个输出：真预期：错误

我真的不确定我哪里出了问题。我尝试使用 result 的 int 和 Integer 类型选项，但没有用。请帮忙。

Answer 1

我看到的问题是 result 变量，因为一旦您将 left 节点的值添加到 result 并完成了 left 子树，那么您会将 right child 的值添加到结果中，这是错误的，因为现在它具有 left 和 right 子值的总和。

所以基本上你是在添加之前的 result 中所有节点的值 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));
    }
}

树-路径总和

Tree - path sum

java

tree

data-structures