import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
// 递归，把sum根据本级节点的值调整后向下传，把是否有符合题意的路径布尔值向上抛，终止条件：空节点或找到路径
// 时空复杂度：O（n）
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if (root == null)
            return false;
        if (root.val == sum && root.left == null && root.right == null)
            return true;
        return (hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val));
    }
}