95. Unique Binary Search Trees II

Leetcode Tree Dynamic Programming

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

分析

如果理解了LeetCode 96. Unique Binary Search Trees的话，这道题目的思路肯定是有的，关键是注意具体的实现细节。

public List<TreeNode> generateTrees(int n) {
    int[] nodeVals = new int[n];
    for (int i = 0; i < n; i++)
        nodeVals[i] = i + 1;
    List<TreeNode> res = constructBinarySearchTree(nodeVals, 0, n);
    return res;    
}

private List<TreeNode> constructBinarySearchTree(int[] nodeVals, int start, int end) {
    List<TreeNode> list = new ArrayList<>();
    // null
    if (start >= end) return list;

    // 只有根节点
    if (start + 1 == end) { list.add(new TreeNode(nodeVals[start])); return list; }

    // 完全在右边
    for (TreeNode rightNode : constructBinarySearchTree(nodeVals, start + 1, end)) {
        TreeNode root = new TreeNode(nodeVals[start]);
        root.left = null;
        root.right = rightNode;
        list.add(root);
    }

    // 完全在左边
    for (TreeNode leftNode : constructBinarySearchTree(nodeVals, start, end - 1)) {
        TreeNode root = new TreeNode(nodeVals[end - 1]);
        root.left = leftNode;
        root.right = null;
        list.add(root);
    }

    // 左右都有
    for (int i = start + 1; i < end - 1; i++){
        for (TreeNode leftNode : constructBinarySearchTree(nodeVals, start, i)) {
            for (TreeNode rightNode : constructBinarySearchTree(nodeVals, i + 1, end)) {
                TreeNode root = new TreeNode(nodeVals[i]);
                root.left = leftNode;
                root.right = rightNode;
                list.add(root);
            }
        }
    }
    return list;
}