第1天

226. 翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null)
            return root;
        TreeNode t = root.left;
        root.left = root.right;
        root.right = t;
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}

116. 填充每个节点的下一个右侧节点指针

class Solution {
    public Node connect(Node root) {
        if(root == null)
            return root;
        connection(root.left, root.right);
        return root;
    }

    void connection(Node left, Node right){
        if(left == null || right == null)
            return;
        left.next = right;
        connection(left.left, left.right);
        connection(right.left, right.right);
        connection(left.right, right.left);
    }
}

114. 二叉树展开为链表

class Solution {
    public void flatten(TreeNode root) {
        if(root == null)
            return;
        flatten(root.left);
        flatten(root.right);

        TreeNode left = root.left;
        TreeNode right = root.right;
        root.right = left;
        root.left = null;

        TreeNode t = root;
        while(t.right != null)
            t = t.right;
        t.right = right;
    }
}

class Solution {
    public void flatten(TreeNode root) {
        TreeNode cur = root;

        while(cur != null){
            if(cur.left != null){
                TreeNode left = cur.left;
                while(left.right != null)
                    left = left.right;
                left.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}

第2天

654. 最大二叉树

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    TreeNode build(int[] nums,int left,int right){
        if(left > right) return null;
        int maxIndex = left;
        for(int i = left; i <= right; i++){
            if(nums[i] > nums[maxIndex]) maxIndex = i;
        }

        TreeNode res = new TreeNode(nums[maxIndex]);

        res.left = build(nums, left, maxIndex - 1);
        res.right = build(nums, maxIndex + 1, right);
        
        return res;
    }
}

105. 从前序与中序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return find(preorder, inorder, 0, 0, inorder.length - 1);
    }

    TreeNode find(int[] preorder, int[] inorder, int preIndex, int inStart, int inEnd){
        if(inStart > inEnd) return null;
        TreeNode res = new TreeNode(preorder[preIndex]);

        int middle = 0;
        for(int i = inStart; i <= inEnd; i++){
            if(inorder[i] == preorder[preIndex]){
                middle = i;
                break;
            }
        }
        res.left = find(preorder, inorder, preIndex + 1, inStart, middle - 1);
        res.right = find(preorder, inorder, preIndex + middle - inStart + 1, middle + 1, inEnd);

        return res;
    }
}

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, Integer.MAX_VALUE + 1L);
    }

    int pre = 0, in = 0;

    TreeNode build(int[] preorder, int[] inorder, long stop){
        if(pre == preorder.length)
            return null;
        if(stop == inorder[in]){
            in++;
            return null;
        }

        TreeNode res = new TreeNode(preorder[pre++]);
        res.left = build(preorder, inorder, res.val);
        res.right = build(preorder, inorder, stop);

        return res;
    }
}

106. 从中序与后序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        in = inorder.length - 1; post = postorder.length - 1;
        return build(inorder, postorder, Integer.MAX_VALUE);
    }

    int in, post;

    TreeNode build(int[] inorder, int[] postorder, long stop){
        if(post < 0)
            return null;
        if(stop == inorder[in]){
            in--;
            return null;
        }

        TreeNode res = new TreeNode(postorder[post--]);
        res.right = build(inorder, postorder, res.val);
        res.left = build(inorder, postorder, stop);

        return res;
    }
}

第3天

652. 寻找重复的子树

class Solution {
    Map<String, Integer> map = new HashMap<>();
    List<TreeNode> res = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return res;
    }

    String traverse(TreeNode root){
        if(root == null)
            return "#";
        
        String left = traverse(root.left);
        String right = traverse(root.right);

        String treStr = left + "," + right + "," + root.val;
        int i = map.getOrDefault(treStr, 0);
        if(i == 1)
            res.add(root);
        map.put(treStr, i + 1);
        return treStr;
    }
}

第4天

230. 二叉搜索树中第K小的元素

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        record = k;
        find(root);
        return res;
    }

    int res;
    int record;

    void find(TreeNode root){
        if(root == null)
            return;

        find(root.left);
        record--;
        if(record == 0){
            res = root.val;
            return;
        }
        
        find(root.right);
    }
}

538. 把二叉搜索树转换为累加树

class Solution {
    int sum = 0;
    public TreeNode convertBST(TreeNode root) {
        exchange(root);
        return root;
    }

    void exchange(TreeNode root){
        if(root == null)
            return;
        exchange(root.right);

        root.val = sum += root.val;
        
        exchange(root.left);
    }
}

第5天

98. 验证二叉搜索树

class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, null, null);
    }

    boolean validate(TreeNode root, TreeNode min, TreeNode max){
        if(root == null)
            return true;
        
        if(min != null && root.val <= min.val)
            return false;
        if(max != null && root.val >= max.val)
            return false;

        return validate(root.left, min, root) && validate(root.right, root, max);
    }
}

700. 二叉搜索树中的搜索

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if(root == null)
            return null;
        if(root.val == val)
            return root;
        else if(val < root.val)
            return searchBST(root.left, val);
        else
            return searchBST(root.right, val);
    }
}

701. 二叉搜索树中的插入操作

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if(root == null)
            return new TreeNode(val);

        if(val > root.val)
            root.right = insertIntoBST(root.right, val);
        else
            root.left = insertIntoBST(root.left, val);
        
        return root;
    }
}

450. 删除二叉搜索树中的节点

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root == null)
            return null;
        
        if(key > root.val)
            root.right = deleteNode(root.right, key);
        else if(key < root.val)
            root.left = deleteNode(root.left, key);
        else{
            if(root.left == null)
                return root.right;
            else if(root.right == null)
                return root.left;

            TreeNode rMin = findRMin(root.right);
            root.val = rMin.val;
            root.right = deleteNode(root.right, rMin.val);
        }

        return root;
    }

    TreeNode findRMin(TreeNode root){
        while(root.left != null)
            root = root.left;
        return root;
    }
}

第6天

96. 不同的二叉搜索树

class Solution {
    int[] dp;
    public int numTrees(int n) {
        dp = new int[n + 1];
        return count(1, n);
    }

    int count(int lo, int hei){
        if(lo >= hei) return 1;

        if(dp[hei - lo + 1] != 0) return dp[hei -lo + 1];

        int res = 0;

        for(int i = lo; i <= hei; i++){
            int left = count(lo, i - 1);
            int right = count(i + 1, hei);
            res += left * right;
        }

        dp[hei - lo + 1] = res;
        return res;
    }
}

95. 不同的二叉搜索树 II

class Solution {
    public List<TreeNode> generateTrees(int n) {
        return build(1, n);
    }

    List<TreeNode> build(int lo, int hei){
        List<TreeNode> res = new ArrayList<>();
        if(lo > hei) {
            res.add(null);
            return res;
        }

        for(int i = lo; i <= hei; i++){
            List<TreeNode> left = build(lo, i - 1);
            List<TreeNode> right = build(i + 1, hei);

            for(TreeNode leftNode : left){
                for(TreeNode rightNode : right){
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    res.add(root);
                }
            }
        }

        return res;
    }
}