Unique Binary Search Tree

题目描述

1. 求数量
2. 求所有可能的树

解题方法

1

如果选取了root为i，那么这个情况下的数量就是左子树的数量 * 右子树的数量。 DP解决

2

recursion解决

对所有的i在[1 - n]区间内,尝试选取每一个点作为root, 然后对它的左边右边再 recursive的去创造节点，recursive function return应该是一个所有可能root的list。

注意：

• 在当前范围不能创造root节点时，应该返回none,作为empty node给上一层

Solution

class Solution(object):
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        if not n:
            return []

        return self.generate(1, n)

    def generate(self, start, end):
        result = []
        if start > end:
            result.append(None)
            return result #到空节点了，可以return了

        for i in range(start, end + 1):
            # pick root，i是被选作root的店
            left_subs = self.generate(start, i - 1) # 左子树递归
            right_subs = self.generate(i+1, end) # 右子树递归

            for l_node in left_subs:
                for r_node in right_subs:
                    root = TreeNode(i) # create a new node
                    root.left = l_node
                    root.right = r_node
                    result.append(root) # add to current list, 是当前子树可以成为root的list
        return result

Reference