[LeetCode]95. 不同的二叉搜索树 II(Unique Binary Search Trees II)

题目描述

给定一个整数 n,生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树:

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

解题思路

递归。以某个数为根节点,可以将原数组分为左子树和右子树两部分,刚好是子问题。

代码

Python 3.6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
if n == 0:
return []
return self.generate_core([i + 1 for i in range(n)])

def generate_core(self, nums):
length = len(nums)
if length == 0:
return [None]
if length == 1:
return [TreeNode(nums[0])]
res = []
for i in range(length):
for left in self.generate_core(nums[:i]):
for right in self.generate_core(nums[i + 1:]):
root = TreeNode(nums[i])
root.left = left
root.right = right
res.append(root)
return res

执行用时 : 116 ms
内存消耗 : 16 MB