Leetcode 95. Unique Binary Search Trees II

https://leetcode.com/problems/unique-binary-search-trees-ii/

DFS.

Solution:

# T:O(4^n/n^(3/2)) S:O(4^n/n^(3/2))
class Solution:
    def dfs(self, start, end):
        if start > end:
            return [None]
        res = []
        for rootVal in xrange(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
    
    def generateTrees(self, n):
        return self.dfs(1, n)

Run Time: 116 ms