每日三题-对称二叉树、从前序与中序遍历序列构造二叉树、不同的二叉搜索树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return fun(root.left,root.right);
    }
    public boolean fun(TreeNode left,TreeNode right){
        if(left == null && right != null) return false;
        if(right == null && left != null) return false;
        if(left == null && right == null) return true;
        if(right.val != left.val) return false;
        return fun(left.left,right.right)&&fun(left.right,right.left);
    }
}

class Solution {
    HashMap<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i = 0;i < inorder.length;i++){
            map.put(inorder[i],i);
        }
        return dfs(preorder,inorder,0,preorder.length-1,0,inorder.length-1);
    }

    public TreeNode dfs(int [] preorder,int []inorder,int left1,int right1,int left2,int right2){
        if(left1 > right1 && left2 > right2) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[left1]);
        int i = map.get(preorder[left1]);
        node.left = dfs(preorder,inorder,left1+1,left1+i-left2,left2,i-1);
        node.right = dfs(preorder,inorder,left1+i-left2+1,right1,i+1,right2);
        return node;
    }
}

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