思路1：使用递归

对于当前节点，只要满足一下任意一个条件即返回true

1. 节点为叶子节点 && 节点值等于sum
2. 节点的左子树 且 sum减去节点的值 能满足条件
3. 节点的右子树 且 sum减去节点的值 能满足条件

public boolean hasPathSum (TreeNode root, int sum) {
  if(root == null){
    return false;
  }
  if (root.left == null && root.right == null){
    if (root.val == sum){
      return true;
    }else{
      return false;
    }
  }
  if (root.val >= sum){
    return false;
  }
  return hasPathSum(root.left, sum-root.val)
    || hasPathSum(root.right, sum-root.val);
}

思路2：使用栈来回溯

回溯需要使用辅助栈判断走到当前这节点时，是应该继续探索左右子树，还是弹出

public boolean hasPathSum (TreeNode root, int sum) {
  if (root == null){
    return false;
  }
  Stack<TreeNode> stack = new Stack<TreeNode>();
  //记录指针走对对应节点时，是什么情况，1：第一次走到，2：左子数回溯而来，3：右子树回溯而来
  Stack<Integer> stack2 = new Stack<Integer>();
  stack.push(root);
  stack2.push(1);
  sum -= root.val;
  while (!stack.isEmpty()){
    TreeNode peek = stack.peek();
    Integer peek2 = stack2.peek();
    if (peek.left == null && peek.right == null && sum == 0){
      return true;
    }
    if (peek2 == 1){
      stack2.pop();
      stack2.push(2);
      //探索左子树
      if (peek.left != null){
        stack.push(peek.left);
        stack2.push(1);
        sum -= peek.left.val;
      }
    }else if (peek2 == 2){
      stack2.pop();
      stack2.push(3);
      //探索右子树
      if (peek.right != null){
        stack.push(peek.right);
        stack2.push(1);
        sum -= peek.right.val;
      }
    }else{
      //左右子树探索完了，弹出
      stack.pop();
      stack2.pop();
      sum += peek.val;
    }
  }
  return false;
}