package LeetCode;

public class LeetCode112 {


    /// 112. Path Sum
    /// https://leetcode.com/problems/path-sum/description/
    /// : O(n), n
    /// : O(h), h


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

    // sum
    // 
    // sum - root.val!!!()
    public boolean hasPathSum(TreeNode root, int sum) {

        if(root == null)
            return false;

        // 
        if(root.left == null && root.right == null)
            return sum == root.val;


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