給定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來緩存構造過的樹形結構。
# 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