1、前言

2、思路

此题可以使用 DFS 递归、BFS 来解题。BFS 的思路其实就是遍历每一层的节点，将每一个条路径的值都加上，所以需要一个额外的队列保存和。
DFS 的思路比较简单，左右两边只要有一处和是 sum 就行。最后的判断条件是要到最后的一个节点，如果最后的节点相减为0，则为 true，否则为 false。对于那种[1,2] 1 那种不算，所以不算 root == null 再判断。

3、代码

DFS：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }

        if(root.left == null && root.right == null){
            return sum - root.val == 0 ? true : false;
        }

        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

BFS：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    // public boolean hasPathSum(TreeNode root, int sum) {
    //     if(root == null){
    //         return false;
    //     }

    //     if(root.left == null && root.right == null && sum - root.val == 0){
    //         return true;
    //     }

    //     return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    // }


    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null){
            return false;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        Queue<Integer> sumQ = new LinkedList<>();

        queue.offer(root);
        sumQ.offer(root.val);

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode cur = queue.poll();
                int curSum = sumQ.poll();

                if(cur.left == null && cur.right == null && curSum == sum){
                    return true;
                }

                if(cur.left != null){
                    queue.offer(cur.left);
                    sumQ.offer(curSum + cur.left.val);
                }

                if(cur.right != null){
                    queue.offer(cur.right);
                    sumQ.offer(curSum + cur.right.val);
                }
            }
        }

        return false;
    }
}