吴良超的学习笔记

LeetCode解题报告(95,96)--构造二叉搜索树

两个题目均是要求利用给出的整数[1, n]构造出所有的二叉搜索树(BST),其中95. Unique Binary Search Trees II要求返回所有的二叉树的根节点,96. Unique Binary Search Trees则仅要求返回所有二叉树的数目。

两个题目均可以通过递归实现,思路如下:
1)遍历[1,n]中每个整数,并将正在遍历的整数 i 设为根节点
2)将 [1,i-1] 的整数构建出来的子树作为整数 i 构建的根节点的左子树,将 [i+1,n] 的整数构造出来的子树作为整数 i 构建的根节点的右子树
3)对得到的左右子树进行组合,这样便可得到以整数i为根节点的所有二叉树

因此,95. Unique Binary Search Trees II实现代码如下:

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
29
30
31
32
# 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 []
return self.helper(1, n)

def helper(self,begin,end):
if begin > end:
return [None]
if begin == end:
return [TreeNode(begin)]
result = []
for i in xrange(begin,end+1):
tmp = []
left = self.helper(begin, i-1)
right = self.helper(i+1, end)
for m in left:
for n in right:
root = TreeNode(i)
root.left, root.right = m, n
result.append(root)
return result

96. Unique Binary Search Trees 的解决思路类似于上面提到的递归的方法,只是这道题目仅仅要求返回二叉树的数量。因此可以通过一个技巧缩短计算量,这个技巧就是整数 i 作为根节点和整数 n-i 作为根节点的时候,两者构造的二叉树的数目是一样的。因此整数 i 作为根节点的左右子树的节点数目与整数 n-i 作为根节点的左右子树的节点数目对称相等。

实现的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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 numTrees(self, n):
"""
:type n: int
:rtype: int
"""

result = 0
if n<=1:
return 1
for i in xrange(n/2):
left = self.numTrees(i)
right = self.numTrees(n-i-1)
result += left * right
result *= 2
if n%2 == 1:
result += pow(self.numTrees(n/2),2)
return result

要注意的是当 n 为基数的时候,整数(n+1)/2没有这种对称关系,需要额外计算。

从上面也可以衍生出动态规划的解法,令 dp[m] 表示 m 个节点能够构造的二叉树的数目。那么dp[m+1]的计算方法如下

1
2
for i in xrange(0, m+1):
dp[m+1] += dp[i]*dp[m+1-i-1]

实现的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""

dp = [0 for i in xrange(n+1)]
dp[0],dp[1] = 1, 1
for i in xrange(2,n+1):
for j in xrange(i):
dp[i] += dp[j]*dp[i-j-1]
return dp[n]