LeetCode解题之Unique Binary Search Trees II

原题

给定1到n这n个数，用它们能够构成多少种形状不同的二叉搜索树。将所有的二叉搜索树罗列出来。

注意点：

• 这n个数都要是二叉搜索树的节点，不能只取部分

例子：

输入: n = 3

输出:

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

解题思路

Unique Binary Search Trees 只要求不同二叉搜索树的数目，现在要求把所有的树的结构都打印出来。所以在递归的时候要把树拼装出来，而不是仅仅计算数目。而且同一个子树可能会在不同的二叉搜索树中多次出现，为了不重复计算，就用一个map来缓存构造过的树形结构。

AC源码

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

    def _generateTrees(self, start, end):
        if (start, end) not in self.cache:
            roots = []
            for root in range(start, end + 1):
                for left in self._generateTrees(start, root - 1):
                    for right in self._generateTrees(root + 1, end):
                        node = TreeNode(root)
                        node.left = left
                        node.right = right
                        roots.append(node)
            self.cache[(start, end)] = roots
        return self.cache[(start, end)] or [None]


if __name__ == "__main__":
    None

欢迎查看我的Github (https://github.com/gavinfish/LeetCode-Python) 来获得相关源码。