先走一步啦（力扣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到的点

• 这段代码属于上一层的回溯代码，而不是本层的回溯代码

]