LeetCode解題之Unique Binary Search Trees II

原題

給定1到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