题目主要信息

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

方法一：递归

具体方法

可以采用深度优先搜索的方式，枚举每一条从根节点到叶子节点的路径。当遍历到叶子节点，且此时路径和恰为目标和时，就找到了一条满足条件的路径。返回true即可。如果不行，则检查左右子节点是否可以有完成路径的，如果任意一条路径可以都返回true，因此这里选用两个子节点递归。

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
       // 如果为null，直接返回false
         if(root==null){
            return false;
        }
      
        else if(root.left==null&&root.right==null){
            return (sum-root.val==0);
        }
      //分别遍历左右子树
        return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
    }
}

复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$，其中 $nn$是树的节点数。在最坏情况下，树的上半部分为链状，下半部分为完全二叉树，并且从根节点到每一个叶子节点的路径都符合题目要求。此时，路径的数目为$O(n)O(n)$，并且每一条路径的节点个数也为 $O(n)O(n)$，因此要将这些路径全部添加进答案中，时间复杂度为 $O(n^2)O(n^2)$。
• 空间复杂度：$O(n)O(n)$，其中 n是树的节点数。空间复杂度主要取决于栈空间的开销，栈中的元素个数不会超过树的节点数。

方法二：深度优先遍历+回溯

具体方法

1、首先，深度优点遍历来说，先写上一个回溯 if (nowroot== null) { return false; }，这表示递归至最深层开始回溯

2、每次进入函数时，将 sum 减去当前节点的权重(nowroot.val)，当 sum 减到零时，说明目标路径存在，另外我们的目标是到叶子节点停止，叶子节点的条件是 nowroot.left == null && nowroot.right == null，所以说当 if (nowroot.left == null && nowroot.right == null && target == 0) ，我们返回 true 表示找到目标路径

3、深度遍历的分支：对于当前节点 curNode 有两个分支，这两个分支都有可能成为目标路径，所以深度优先遍历的写法为 return dfs(nowroot.left, target) || dfs(nowroot.right, target);

4、现在来谈谈为什么回溯时需要返回 false，因为当 nowroot 为叶子节点时，并且 sum == 0 时，我们已经返回了 true，剩下的情况就是nowroot不是叶子节点或者路径值不为 target，所应该返回 false

Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null){
            return false;
        }
        //使用深度优先遍历
        return dfs(root,sum);
    }
    public boolean dfs(TreeNode nowroot,int sum){
        if(nowroot == null){
            return false;
        }
        //更新和
        sum -= nowroot.val;
                // 当当前节点为叶子节点并且目标路径存在时，返回 true
        if (nowroot.left == null && nowroot.right == null && sum == 0) {
            return true;
        }
        // 对左右分支进行 dfs
        return dfs(nowroot.left, sum) || dfs(nowroot.right, sum);
    }
}

复杂度分析

• 时间复杂度 :$O(n)O(n)$ n为二叉树的节点数，最差的情况递归所有节点。
• 空间复杂度 :$O(n)O(n)$ 不需要额外空间