Alibi

My Life is Getting Better

Leetcode[95, 96] Unique Binary Search Trees

07 Nov 2015

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

For example, Given n = 3, there are a total of 5 unique BST’s.

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

###Python

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0 for i in range(n + 1)]
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] += dp[j] * dp[i - j - 1] 
                # num of left + num of right = i - 1, root is not included
        return dp[n]

###Java

/*
	Too stupid to figure this out:
	以任何节点为根所有bst的可能性等于左子树的可能乘以右子树的可能情况
*/

public class Solution {
    public int numTrees(int n) {
        if (n < 0) {
        	return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
        	dp[i] = 0;
        	for (int j = 0; j < i; j++) {
        		dp[i] += dp[j] * dp[i - j - 1];
        	}
        }

        return dp[n];
    }

    // public static void main(String[] args) {
    // 	Solution sol = new Solution();
    // 	System.out.println(sol.numTrees(4));
    // }
}

###Points

总时间复杂度是O(1+2+…+n)=O(n^2)。空间上需要一个数组来维护，并且需要前i个的所有信息，所以是O(n)

###Task2 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

###Python

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if n < 1:
            return [[]]
        return self.findAll(1, n)
    
    def findAll(self, start, end):
        ret = []
        if start > end:
            ret.append(None)
            return ret
        for i in range(start, end + 1):
            l = self.findAll(start, i - 1)
            r = self.findAll(i + 1, end)
            for le in l:
                for ri in r:
                    root = TreeNode(i)
                    root.left = le
                    root.right = ri
                    ret.append(root)
        return ret

###Java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * 
 * 知道是dfs， 但是怎么写
 * DIVEDE AND CONQUER!
 * 怎么分成左右子树
 * 左子树包括所有小于的数，同理
 * 
 */
public class Solution {

	public List<TreeNode> treeHelper(int start, int end) {
		List<TreeNode> root = new ArrayList<TreeNode>();
		if (start > end) {
			root.add(null);
			return root;
		}

		for (int i = start; i <= end; i++) {
			List<TreeNode> left = treeHelper(start, i - 1);
			List<TreeNode> right = treeHelper(i + 1, end);
			for (int j = 0; j < left.size(); j++) {
				for (int k = 0; k < right.size(); k++) {
					TreeNode node = new TreeNode(i);
					node.left = left.get(j);
					node.right = right.get(k);
					root.add(node);
				}
			}
		}

		return root;
	}

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

        return treeHelper(1, n);
    }
}

###Points

Related Posts