class Solution {
    // 递归宏观语义：返回以root为根节点的二叉树，从根节点到叶子结点 其和为sum的路径是否存在
    // 时间复杂度O(N)  空间复杂度O(N) 递归栈的大小
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) { 
            return false;
        }
        if (root.left == null && root.right == null) { // 递归到叶子结点 看剩下的sum是否等于叶子结点的值
            return root.val == sum;
        }
        // 去左子树找是否存在这样的路径并更新sum的值 去右子树找是否存在这样的路径并更新sum的值 只有左右子树有一个找到了 就返回true
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);  
    }
}

class Solution {
    // BFS 时间复杂度O(N)  空间复杂度O(M):队列大小
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {  // 树空
            return false;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode front = queue.poll();
            if (front.left == null && front.right == null) {  // 遍历到叶节点
                if (front.val == sum) { // 只有当从根节点到该叶节点路径上的和累加起来 == sum
                    return true;
                }
            }
            if (front.left != null) { // 左子树不空 左孩子入队 并将父亲结点的值累加到左孩子结点
                front.left.val += front.val; 
                queue.offer(front.left);
            }
            if (front.right != null) { // 右子树不空 右孩子入队 并将父亲结点的值累加到右孩子结点
                front.right.val += front.val;
                queue.offer(front.right);
            }
        }
       return false; 
    }
}