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]