卖萌的弱渣

I am stupid, I am hungry.

Unique Binary Search Tree II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

Example

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

1
2
3
4
5

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

Solution

  • DFS search the left and right subtrees. Then merge the trees.
(Unique-Binary-Search-Trees2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    # @paramn n: An integer
    # @return: A list of root
    def generateTrees(self, n):
        # write your code here
        return self.dfs(1, n)

    def dfs(self, start, end):
        if start > end: return [None]
        res = []
        for rootval in range(start, end+1):
            LeftTree = self.dfs(start, rootval-1)
            RightTree = self.dfs(rootval+1, end)
            for i in LeftTree:
                for j in RightTree:
                    root = TreeNode(rootval)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res