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

思考的問(wèn)題

• 記一次對(duì)該解題代碼的位置擺放

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

// carl哥的回溯解題法，// 略微有些改動(dòng)，其實(shí)就是把    // return traversal(root, targetSum-root.val);// 的targetSum-root.val，放在了外面，對(duì)我來(lái)說(shuō)這更清晰些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){          // 當(dāng)為葉子節(jié)點(diǎn)時(shí)，如果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)){              // 如果子樹(shù)找到了，那就直接返回true              return true;          }          count+=root.right.val;      }      return false;  }}

來(lái)討論終止條件

終止條件是root位于葉子結(jié)點(diǎn)才終止（這里先不討論count）
如果root為null作為終止條件，是會(huì)判錯(cuò)的。

舉個(gè)例子

1 targetsum=1

2

可以看到當(dāng)進(jìn)入右子樹(shù)時(shí)，

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

來(lái)討論count

我們?cè)賮?lái)討論count

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

1. count為0時(shí)

? 如果count為0時(shí)正確，那么需要提前減去當(dāng)前節(jié)點(diǎn)值，

? 也就是進(jìn)入循環(huán)之前減去root值。

? 舉個(gè)例子

? 1 targetsum=1 只有一個(gè)根節(jié)點(diǎn)的樹(shù)

? / /

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

? 那么進(jìn)入回溯的if判斷就不會(huì)成功返回true

解題代碼的擺放位置

? 有同學(xué)可能會(huì)想我把減去當(dāng)前root值的條件放在這里怎么樣

當(dāng)然是可以的，只不過(guò)我們需要對(duì)整道題作些調(diào)整。

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){            // 當(dāng)為葉子節(jié)點(diǎn)時(shí)，如果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)){                // 如果子樹(shù)找到了，那就直接返回true                return true;            }            count+=root.right.val;        }        return false;    }}

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

? 然后我們要把count變成全局變量，因?yàn)槲挥诤瘮?shù)參數(shù)的count是一個(gè)局部變量，它在下一層函數(shù)中減去了root.left.val，count+=root.left.val的目的就是為了把它加回來(lái)。然而如果他是局部變量，我們就加在了本層函數(shù)的局部變量count里，而不是下層函數(shù)的count。

?

? 那么把count+=root.left.val，變成count+=root.val行不行呢，當(dāng)然是不行的，因?yàn)檫@層函數(shù)減去的root.val是上一層函數(shù)的root.left.val。

? 根節(jié)點(diǎn)剛進(jìn)來(lái)時(shí)屬于一種特殊情況。

2. count為root.val時(shí)

? 如果count為root.val時(shí)正確

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){            // 當(dāng)為葉子節(jié)點(diǎn)時(shí)，如果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)){                // 如果子樹(shù)找到了，那就直接返回true                return true;            }            count+=root.val;        }        return false;    }}

總結(jié)和個(gè)人感悟

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

? 個(gè)人感悟：對(duì)一顆樹(shù)的完整思考是，從根節(jié)點(diǎn)出發(fā)，到左子樹(shù)，進(jìn)入下一層循環(huán)，看一眼終止條件，就可以回到上一層循環(huán)，不用在繼續(xù)往下走了，就可以驗(yàn)證解題代碼是否正確的

get到的點(diǎn)

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

]