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);
    }
}