Unique Binary Search Trees I & II

To calculate the number of trees, use the recursive solution, but the number of total subtrees can be calculated by multiplying number of left and right subtrees, so here comes the code

public class Solution {
    public int numTrees(int n) {
        return numSubTree(1, n);
    }
    
    private int numSubTree(int start, int end) {
        if (start > end)
            return 1;
        int res = 0;
        for (int i = start; i <= end; i++) {
            res += numSubTree(start, i-1) * numSubTree(i+1, end);
        }
        return res;
    }
}

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

这道题只需要recursive的求解即可,每个array中挑出一个数作为head,剩下左边的recursive求左子数,右边的recursive求右子树,注意处理两头的情况,有一边子树为0

另外注意return结果的时候每次需要新建一个head,和新生成的两个子树加在一起,最后加入result array并return。

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; left = null; right = null; }
 * }
 */
public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        if (n < 1)
        {
            res.add(null);
            return res;
        }
        return buildTree(1, n);
    }
    
    public ArrayList<TreeNode> buildTree(int start, int end)// generate tree from start to end inclusive
    {
        ArrayList<TreeNode> res = new ArrayList<TreeNode>();
        if (start == end)
        {
            TreeNode t = new TreeNode(start);
            res.add(t);
            return res;
        }
        
        for (TreeNode n : buildTree(start+1, end))
        {
            TreeNode head = new TreeNode(start); // build a new head for every subtree
            head.left = null;
            head.right = n;
            res.add(head);
        }
        
        for (int i = start + 1; i < end; i++)
        {
            for (TreeNode l : buildTree(start, i-1))
            {
                for (TreeNode r: buildTree(i+1, end))
                {
                    TreeNode head = new TreeNode(i);
                    head.left = l;
                    head.right = r;
                    res.add(head);
                }
            }
        }
        
        for (TreeNode n : buildTree(start, end - 1))
        {
            TreeNode head = new TreeNode(end); 
            head.left = n;
            head.right = null;
            res.add(head);
        }
        return res;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s