先走一步啦（力扣112路徑總和），對解題代碼的深入思考

思考的問題

• 記一次對該解題代碼的位置擺放

• 和count==?的深入思考。

// carl哥的回溯解題法，// 略微有些改動，其實就是把    // return traversal(root, targetSum-root.val);// 的targetSum-root.val，放在了外面，對我來說這更清晰些class Solution {  public boolean hasPathSum(TreeNode root, int targetSum) {    if(root==null){      return false;    }    // 先走一步啦    targetSum-=root.val;    return traversal(root, targetSum);  }  private boolean traversal(TreeNode root, int count){      if(root.left==null && root.right==null && count==0){          // 當為葉子節點時，如果count為0就返回true          return true;      }      if(root.left!=null){          count-=root.left.val;          if(traversal(root.left, count)){              return true;          }          count+=root.left.val;      }      if(root.right!=null){          count-=root.right.val;          if(traversal(root.right, count)){              // 如果子樹找到了，那就直接返回true              return true;          }          count+=root.right.val;      }      return false;  }}

來討論終止條件

終止條件是root位于葉子結點才終止（這里先不討論count）
如果root為null作為終止條件，是會判錯的。

舉個例子

1 targetsum=1

2

可以看到當進入右子樹時，

此時為null，就返回true了，顯然并不是正確的答案。

來討論count

我們再來討論count

count 也是我們判斷是否是正確路徑的條件之一

1. count為0時

? 如果count為0時正確，那么需要提前減去當前節點值，

? 也就是進入循環之前減去root值。

? 舉個例子

? 1 targetsum=1 只有一個根節點的樹

? / /

? [1]就是一條路徑，如果我們不先減去root的值，

? 那么進入回溯的if判斷就不會成功返回true

解題代碼的擺放位置

? 有同學可能會想我把減去當前root值的條件放在這里怎么樣

當然是可以的，只不過我們需要對整道題作些調整。

class Solution {    public boolean hasPathSum(TreeNode root, int targetSum) {        if(root==null){            return false;        }        count=targetSum;        return traversal(root);    }    int count;    private boolean traversal(TreeNode root){        count-=root.val;        if(root.left==null && root.right==null && count==0){            // 當為葉子節點時，如果count為0就返回true            return true;        }                if(root.left!=null){            if(traversal(root.left)){                return true;            }            count+=root.left.val;        }        if(root.right!=null){            if(traversal(root.right)){                // 如果子樹找到了，那就直接返回true                return true;            }            count+=root.right.val;        }        return false;    }}

? 我們首先選擇把位于這里的代碼刪去，如果不刪去的話進入下一層循環就相當于減去了兩次root.left.val

? 然后我們要把count變成全局變量，因為位于函數參數的count是一個局部變量，它在下一層函數中減去了root.left.val，count+=root.left.val的目的就是為了把它加回來。然而如果他是局部變量，我們就加在了本層函數的局部變量count里，而不是下層函數的count。

?

? 那么把count+=root.left.val，變成count+=root.val行不行呢，當然是不行的，因為這層函數減去的root.val是上一層函數的root.left.val。

? 根節點剛進來時屬于一種特殊情況。

2. count為root.val時

? 如果count為root.val時正確

class Solution {    public boolean hasPathSum(TreeNode root, int targetSum) {        if(root==null){            return false;        }        return traversal(root, targetSum);    }    private boolean traversal(TreeNode root, int count){        if(root.left==null && root.right==null && count==root.val){            // 當為葉子節點時，如果count為root.val就返回true            return true;        }        if(root.left!=null){            count-=root.val;            if(traversal(root.left, count)){                return true;            }            count+=root.val;        }        if(root.right!=null){            count-=root.val;            if(traversal(root.right, count)){                // 如果子樹找到了，那就直接返回true                return true;            }            count+=root.val;        }        return false;    }}

總結和個人感悟

總結：使用遞歸解題，代碼的擺放位置和終止條件的選擇都對編碼方式有著巨大的影響

? 個人感悟：對一顆樹的完整思考是，從根節點出發，到左子樹，進入下一層循環，看一眼終止條件，就可以回到上一層循環，不用在繼續往下走了，就可以驗證解題代碼是否正確的

get到的點

• 這段代碼屬于上一層的回溯代碼，而不是本層的回溯代碼

]