樹 - 路徑總和

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