class Solution {
    public List<TreeNode> generateTrees(int n) {
        if (n == 0) {
            return new LinkedList<TreeNode>();
        }
        List<TreeNode> res = add(1, n);
        return res;
    }

    public List<TreeNode> add(int left,int right){
        List<TreeNode> res = new LinkedList<>();
        if(left > right){
            res.add(null);
            return res;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftList = add(left, i - 1);
            List<TreeNode> rightList = add(i + 1, right);
            for (TreeNode leftTree : leftList) {
                for (TreeNode rightTree : rightList) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftTree;
                    root.right = rightTree;
                    res.add(root);
                }
            }
        }
        return res;
    }
}

class Solution {
    public int numTrees(int n) {
        if(n == 0) return 0;
        int[] count = new int[n + 1];
        count[0] = 1;
        count[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            for (int j = 0,k = i - 1; j < i; j++,k--) {
                count[i] += count[j] * count[k];
            }
        }
        return count[n];
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        return inSpread(root,(long)Integer.MIN_VALUE - 1,(long)Integer.MAX_VALUE + 1);
    }
    boolean inSpread(TreeNode node,long left,long right){
        if(node.val <= left || node.val >= right){
            return false;
        }
        if(node.left != null){
            if(!inSpread(node.left, left, node.val)) return false;
        }
        if(node.right != null){
            if(!inSpread(node.right, node.val, right)) return false;
        }
        return true;
    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
		int i = nums.length / 2;
		TreeNode res = new TreeNode(nums[i]);
		res.left = build(nums,0,i - 1);
		res.right = build(nums,i + 1,nums.length - 1);
		return res;
    }

	public TreeNode build(int[] nums, int left, int right) {
		if(left > right) return null;
		else {
			int i = (left + right) / 2;
			TreeNode node = new TreeNode(nums[i]);
			node.left = build(nums,left,i - 1);
			node.right = build(nums,i + 1,right);
			return node;
		}
	}
}