java - 树-路径总和

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,空,-1]3输出:真预期:错误

我真的不知道我哪里出了问题。我尝试使用 result 的 int 和 Integer 类型选项，但它不起作用。请帮忙。

Answer 1

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

因此，本质上您是在将之前的结果中的所有节点的值相加中序遍历中的节点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));
    }
}