Question

Formatted question description: https://leetcode.ca/all/95.html

95	Unique Binary Search Trees II

Given n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

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

@tag-tree
@tag-divideconquer

Algorithm

This kind of tree building problem is generally solved by recursion, and this problem is no exception, dividing the left and right subtrees, and recursive construction.

This actually uses the well-known divide and conquer method Divide and Conquer, and similar problems are the same as the previous Different Ways to Add Parentheses method, using recursion to solve, dividing the left and right sub-arrays, recursive construction.

At the beginning, consider the interval [1, n] as a whole, and then you need to treat each number as the root node, which divides the left and right sub-intervals, and then call the recursive function separately, you will get two Node array, the next thing to do is to take one node each time from these two arrays, as the left and right child nodes of the current root node, and then add the root node to the result array.

Pitfalls

  1. When start>end, if you directly return an empty list, size=0, then inserting the left and right subtrees will not work, i=0, i<left.size() loop will not enter So I use if-else to determine whether the list is empty So you must add a null to the list, let size=1

  2. To create a root node, it must be in two for loops, because each time is an independent tree. I created the root node first, and then went into the for loop, but the result was repeated, because each for was operated on the same tree, and the added tree was changed.

I thought of the idea of creating left and right subtrees, but I didn’t figure out how to implement it and how to return the built subtrees to the upper level. This generate(start, end) is great.

Code

Java

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

public class Unique_Binary_Search_Trees_II {

    public static void main(String[] args) {
        Unique_Binary_Search_Trees_II out = new Unique_Binary_Search_Trees_II();
        Solution s = out.new Solution();

        for (TreeNode each: s.generateTrees(3)) {
            System.out.println(each);
        }
    }

	/**
	 * Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode(int x) { val = x; }
	 * }
	 */

    // optimized
    public class Solution {

        public List<TreeNode> generateTrees(int n) {
            if (n == 0) {
                return new ArrayList<TreeNode>();
            }

            return generate(1, n);
        }

        public ArrayList<TreeNode> generate(int start, int end) {

            ArrayList<TreeNode> result = new ArrayList<TreeNode>();

            if (start > end) {
                result.add(null); // @note:@memorize:这里就是空的左树或者右树,是关键
                return result;
            }

            for (int i = start; i <= end; i++) {

                // i as root
                ArrayList<TreeNode> left = generate(start, i - 1);
                ArrayList<TreeNode> right = generate(i + 1, end);

                // append left subtree and right subtree
                // @note@note: should put inside for looping!, or, reference is modified onstantly!
                for (TreeNode l : left) {
                    for (TreeNode r : right) {

                        // 每次都要复制一个
                        TreeNode currentRoot = new TreeNode(i); // 当前的i作为head node

                        currentRoot.left = l;
                        currentRoot.right = r;

                        result.add(currentRoot);
                    }
                }
            }

            return result;
        }

    }

    // DP version
    public class Solution_iterative {

        public List<TreeNode> generateTrees(int n) {

            if (n == 0) {
                return new ArrayList<TreeNode>();
            }

            @SuppressWarnings("unchecked")
            List<TreeNode>[] result = new ArrayList[n + 1]; // @note: just like: new int[10]

            result[0] = new ArrayList<TreeNode>(); // empty tree
            result[0].add(null);

            for (int i = 1; i <= n; i++) {
                result[i] = new ArrayList<TreeNode>(); // store all combinations when n is i

                for (int leftIndex = 0; leftIndex < i; leftIndex++) {
                    for (TreeNode leftSub : result[leftIndex]) { // get ONE left subtree
                        for (TreeNode rightSub : result[i - leftIndex - 1]) { // get One right subtree
                            TreeNode tmpRoot = new TreeNode(leftIndex + 1);
                            tmpRoot.left = leftSub;

                            // @note:@memorize: key is here. should generate right subtree, where the start number is "1 + leftIndex"
                            tmpRoot.right = clone(rightSub, leftIndex + 1);
                            result[i].add(tmpRoot);
                        }
                    }
                }
            }
            return result[n];
        }

        // apply offset is still a local recursion
        private TreeNode clone(TreeNode n, int offset) { // name is nice, self-explanatory

            if (n == null) return null;
            TreeNode node = new TreeNode(n.val + offset);
            node.left = clone(n.left, offset);
            node.right = clone(n.right, offset);
            return node;
        }

    }
}

All Problems

All Solutions