LeetCode（95 & 96）：不同的二叉搜尋樹 I II Unique Binary Search Trees I II（Java）

2019.8.17 #程式員筆試必備# LeetCode 從零單刷個人筆記整理（持續更新）

在給定一個整數n，第一道題要求算出能夠組成的二叉搜尋樹的數量，第二道題要求生成所有不同的二叉搜尋樹。

大題思路相同，對于序列1-n，依次取不同的數字作為根節點，根節點将序列分為左右兩段，分别為根節點的左子樹和右子樹。若左半段能夠有m種不同組合，右半段有n種不同組合，根節點構成的不同二叉搜尋樹有m*n種。

遞歸是最基本的解決二叉樹問題的通用算法，不過在n較大的情況下，可以考慮用動态規劃做。

dp[i] += dp[j] * dp[i - 1 - j];
           

如果需要生成子樹，就涉及到深拷貝，需要寫一個遞歸函數專門用于深拷貝。左子樹可以複用，隻需要對所有右子樹深拷貝即可。

傳送門：不同的二叉搜尋樹

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

給定一個整數 n，求以 1 … n 為節點組成的二叉搜尋樹有多少種？

示例:

輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結構的二叉搜尋樹:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

           

傳送門：不同的二叉搜尋樹 II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.

給定一個整數 n，生成所有由 1 … n 為節點所組成的二叉搜尋樹。

示例:

輸入: 3
輸出:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
解釋:
以上的輸出對應以下 5 種不同結構的二叉搜尋樹：

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

           

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
 * 給定一個整數 n，求以 1 ... n 為節點組成的二叉搜尋樹有多少種？
 * Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.
 * 給定一個整數 n，生成所有由 1 ... n 為節點所組成的二叉搜尋樹。
 */

public class UniqueBinarySearchTrees {
    //遞歸：逾時
    public int numTrees(int n) {
        if (n <= 1) {
            return 1;
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result += numTrees(i) * numTrees(n - 1 - i);
        }
        return result;
    }

    //動态規劃
    public int numTrees2(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }
        return dp[n];
    }

    //數學歸納法
    public int numTrees3(int n) {
        long result = 1;
        for (int i = 0; i < n; i++) {
            result = result * 2 * (2 * i + 1) / (i + 2);
        }
        return (int) result;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    //傳回所有二叉搜尋樹
    //遞歸
    public List<TreeNode> generateTrees(int n) {
        if(n == 0){
            return new LinkedList<>();
        }
        return Solution(1, n);
    }

    public LinkedList<TreeNode> Solution(int begin, int end){
        LinkedList<TreeNode> result = new LinkedList<>();
        if(begin > end){
            result.add(null);
            return result;
        }

        for(int i = begin; i <= end; i++){
            LinkedList<TreeNode> leftTree = Solution(begin, i - 1);
            LinkedList<TreeNode> rightTree = Solution(i + 1, end);
            for(TreeNode left : leftTree){
                for(TreeNode right : rightTree){
                    TreeNode curTree = new TreeNode(i);
                    curTree.left = left;
                    curTree.right = right;
                    result.add(curTree);
                }
            }
        }

        return result;
    }

    //動态規劃
    public List<TreeNode> generateTrees2(int n){
        ArrayList<TreeNode>[] dp = new ArrayList[n + 1];
        dp[0] = new ArrayList<>();
        if(n == 0){
            return dp[0];
        }

        dp[0].add(null);
        for(int len = 1; len <= n; len++){
            dp[len] = new ArrayList<>();
            for(int root = 1; root <= len; root++){
                int leftLen = root - 1;
                int rightLen = len - root;
                for(TreeNode leftTree : dp[leftLen]){
                    for(TreeNode rightTree : dp[rightLen]){
                        TreeNode treeRoot = new TreeNode(root);
                        treeRoot.left = leftTree;
                        treeRoot.right = clone(rightTree, root);
                        dp[len].add(treeRoot);
                    }
                }
            }
        }

        return dp[n];
    }

    //克隆右子樹并且加上偏差
    public TreeNode clone(TreeNode n, int offset){
        if(n == null){
            return n;
        }
        TreeNode node = new TreeNode(n.val + offset);
        node.left = clone(n.left, offset);
        node.right = clone(n.right, offset);
        return node;
    }
}



           

#Coding一小時，Copying一秒鐘。留個言點個贊呗，謝謝你#