95. Unique Binary Search Trees II

Question

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

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

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

Thinking:

• Method 1:回溯，会出现重复问题。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<>();
        boolean[] used = new boolean[n];
        if(n == 0) return result;
        generateTrees(n, result, used, null);
        return result;
    }
    private void generateTrees(int n, List<TreeNode> result, boolean[] used, TreeNode root){
        if(n == 0){
            result.add(copyTree(root));
            return;  
        } 
        else{
            for(int i = 0; i < used.length; i++){
                if(used[i]) continue;
                used[i] = true;
                if(n == used.length){
                    TreeNode tempRoot = new TreeNode(i + 1);
                    generateTrees(n - 1, result, used, tempRoot);
                }else{
                    addTreeNode(root, new TreeNode(i + 1));
                    generateTrees(n - 1, result, used, root);
                    removeNode(root, i + 1);
                }
                used[i] = false;
            }
        }
    }
    private void removeNode(TreeNode root, int val){
        if(root == null) return;
        if(val < root.val){
            if(root.left.val == val){
                root.left = null;
                return;
            }
            removeNode(root.left, val);
        }else{
            if(root.right.val == val){
                root.right = null;
                return;
            }
            removeNode(root.right, val);
        }
    }
    private TreeNode copyTree(TreeNode root){
        if(root == null) return null;
        TreeNode result = new TreeNode(root.val);
        if(root.left != null) result.left = copyTree(root.left);
        if(root.right != null) result.right = copyTree(root.right);
        return result;
    }
    private void addTreeNode(TreeNode root, TreeNode node){
        if(node.val < root.val){
            if(root.left == null)
                root.left = node;
            else
                addTreeNode(root.left, node);
        }
        else{
            if(root.right == null)
                root.right = node;
            else
                addTreeNode(root.right, node);
        }
    }
}

• Method 2: DP
  • 参考96. Unique Binary Search Trees
  • 我们将dp运用在List数组上。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode>[] result = new List[n + 1];
        result[0] = new ArrayList<TreeNode>();
        if(n == 0) return result[0];
        result[0].add(null);
        for(int i = 1; i <= n; i++){
            result[i] = new ArrayList<>();
            for(int j = 0; j < i; j++){
                List<TreeNode> lefts = result[j];
                List<TreeNode> rights = result[i - 1 - j];
                for(TreeNode left : lefts){
                    for(TreeNode right : rights){
                        TreeNode root = new TreeNode(j + 1);
                        root.left = left;
                        root.right = copyTree(right, j+1);
                        result[i].add(root);
                    }
                }
            }
        }
        return result[n];
    }
    private TreeNode copyTree(TreeNode root, int offset){
        if(root == null) return null;
        TreeNode node = new TreeNode(root.val + offset);
        node.left = copyTree(root.left, offset);
        node.right = copyTree(root.right, offset);
        return node;
    }
}