树 - 路径总和

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] 输出：true 预计：假

我真的不知道我在哪里出错了。我尝试使用int和Integer类型选项来获得结果，但它不起作用。请帮忙。

Answer 1

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

所以基本上你在 在inorder遍历节点root之前来的result将所有的节点的值。

你可以试试这个：

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)); 
    } 
}