Unique Binary Search Trees II

Problem Id: 95 Difficulty: Medium Tag: Dynamic Programming Tag: Tree


Intuition

This is a typical DP problem which could be solved recursivly.

Let's start from the defination of binary search tree. For each node, the nodes on its left sub-tree is always less than itself. And nodes on its right sub-tree is always greater than itself.

So, by choosing a root value from n nodes, the numbers would be grouped into 2 sets. Smaller set is all on its left and bigger set is all on its right. That how this solution comes from.

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):
        if n <= 0:
            return []
        self.cache = {}
        return self._dfs(0, n + 1)

    def _dfs(self, lo, hi):
        if hi - lo == 1:
            return [None]
        if (lo, hi) not in self.cache:
            ans = []
            for mid in range(lo + 1, hi):
                for left in self._dfs(lo, mid):
                    for right in self._dfs(mid, hi):
                        current = TreeNode(mid)
                        current.left = left
                        current.right = right
                        ans.append(current)
            self.cache[(lo, hi)] = ans
        return self.cache[(lo, hi)]