Unique Binary Search Tree 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

解题方法

跟上一题的思想类似，但是这里用到递归的方法来获得具体的子树，然后对于左右两边的所有组合可能都添加到结果里

注意点

• 边界条件的处理
  • 当start < end时，正常处理
  • 当start == end时，说明只剩下一个数字可用，也就只有一种子树了
  • 当start > end时，说明就是上个recusive call里选了start或者end做root,那么左/右 子树就应该是None,返回None
• python变量，每次都应该建一个新的加到结果里，不然Python会复用同一变量，最终得到的结果就不对了，就像subsets题目里一样

Solution

# 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]
        """
        return self.generate(1, n)

    def generate(self, start, end):
        result = []
        if start > end:
            # means no possible subtrees
            # should return None to above to make the left/right child None
            result.append(None)
            return result

        for i in range(start, end+1):
            leftSubs = self.generate(start, i-1)
            rightSubs = self.generate(i+1, end)

            for l in leftSubs:
                for r in rightSubs:
                    root = TreeNode(i) # should make a root everytime, otherwise it would change with for-loops
                    root.left = l
                    root.right = r
                    result.append(root)

        return result

Reference