LeetCode 95. 不同的二叉搜索树 II（中）

在二叉树上做动态规划，值得好好学习学习的一道题。

题目

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

示例

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入: 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

考察知识点

动态规划、二叉搜索树

核心思想

方法一、动态规划

当 n=3 时，有以下情况：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
空树时的解个数：None（空树也认为是一种树）[卡塔兰数 C_0=1]
只有一个节点时所有解：1、2、3（全部为根节点）[卡塔兰数 C_1=1*3]
两个节点时所有解（我们只需要考虑连续数字）：[卡塔兰数 C_2=2*2]
[ 1 2 ]
  1  
   \    
    2
   2
  /
 1
    
[ 2 3 ]
  2  
   \    
    3
   3
  /
 2
 
三个节点时的所有情况：[卡塔兰数 C_3=5]
[ 1 2 3 ]
利用递归的思路，就是分别把每个数字作为根节点，然后考虑左子树和右子树的可能
1 作为根节点，左子树是 [] 的所有可能，右子树是 [ 2 3 ] 的所有可能，利用之前求出的结果进行组合。
    1
  /   \
null   2
        \
         3

    1
  /   \
null   3
      /
     2 

2 作为根节点，左子树是 [ 1 ] 的所有可能，右子树是  [ 3 ] 的所有可能，利用之前求出的结果进行组合。
    2
  /   \
 1     3

3 作为根节点，左子树是 [ 1 2 ] 的所有可能，右子树是 [] 的所有可能，利用之前求出的结果进行组合。
     3
   /   \
  1   null
   \
    2

      3
    /   \
   2   null 
  /
 1

然后利用上边的思路基本上可以写代码了，就是求出长度为 1 的所有可能，长度为 2 的所有可能 ... 直到长度为 n 的所有可能。
我们注意到，求长度为 3 的所有可能的时候，我们需要先求 [ 1 2 ] 的所有可能，[ 2 3 ] 的所有可能，这只是 n = 3 的情况。如果 n 等于 100，我们需要求的更多了 [ 1 2 ] ， [ 2 3 ] ， [ 3 4 ] ... [ 99 100 ] 太多了。能不能优化呢？
仔细观察，我们可以发现长度是为 2 的所有可能其实只有两种结构。

1
2
3
4
5
6
7
  x  
 /    
y

y
 \
  x

对比前推导的 [ 1 2 ] 和 [ 2 3 ]，只是数字不一样，结构是完全一样的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
[ 1 2 ]
  1  
   \    
    2
   2
  /
 1
    
[ 2 3 ]
  2  
   \    
    3
   3
  /
 2

所以我们 n = 100 的时候，求长度是 2 的所有情况的时候，我们没必要把 [ 1 2 ] ， [ 2 3 ] ， [ 3 4 ] ... [ 99 100 ] 所有的情况都求出来，只需要求出 [ 1 2 ] 的所有情况即可。
推广到任意长度 len，我们其实只需要求 [ 1 2 ... len ] 的所有情况就可以了。下一个问题随之而来，这些 [ 2 3 ] ， [ 3 4 ] ... [ 99 100 ] 没求的怎么办呢？
举个例子，我们已经递推得到了[ 1 2 ... 99]的所有情况，当n = 100，此时我们求把 98 作为根节点的所有情况，根据之前的推导，我们需要长度是 97 的 [ 1 2 ... 97 ] 的所有情况作为左子树，长度是 2 的 [ 99 100 ] 的所有情况作为右子树。
既然已经求到了 [ 1 2 ... 99 ]的所有情况，那么前面 [ 1 2 ... 97 ] 的所有情况也已经求出来了。但 [ 99 100 ] 怎么办呢？我们只求了 [ 1 2 ] 的所有情况。答案很明显了，在 [ 1 2 ] 的所有情况每个数字加一个偏差 98，即加上根节点的值就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[ 1 2 ]
  1  
   \    
    2
   2
  /
 1
    
[ 99 100 ]
  1 + 98
   \    
    2 + 98
   2 + 98
  /
 1 + 98

即
  99  
   \    
    100
   100
  /
 99

所以我们需要一个函数，实现树的复制并且加上偏差。

1
2
3
4
5
6
def clone(self, n: TreeNode, offset: int) -> TreeNode:
    if n == None:  return None
    node = TreeNode(n.val + offset)
    node.left = self.clone(n.left, offset)
    node.right = self.clone(n.right, offset)
    return node

通过上边的所有分析，代码可以写了，总体思想就是求长度为 2 的所有情况，求长度为 3 的所有情况直到 n。而求长度为 k（例如k=2） 的所有情况，我们只需要求出一个代表 [ 1 2 ... k ]（ 例如 [1, 2] ） 的所有情况，其他的话加上一个偏差，加上当前根节点即可。

Python版本

  • 方法一动态规划的实现 比较容易理解的动态规划实现
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
from typing import List

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:

    def clone(self, n: TreeNode, offset: int) -> TreeNode:
        if n == None:  return None
        node = TreeNode(n.val + offset)
        node.left = self.clone(n.left, offset)
        node.right = self.clone(n.right, offset)
        return node

    def generateTrees(self, n: int) -> List[TreeNode]:
        dp = [[] for _ in range(n + 1)] 
        dp[0] = []
        if n == 0:  return dp[0]
        dp[0].append(None)  # 卡塔兰数第0个
        for len in range(1, n+1):  # len是当前要求解的节点个数 
            dp[len] = []
            for root in range(1, len + 1):
                left = root - 1
                right = len - root
                for leftTree in dp[left]:
                    for rightTree in dp[right]:
                        treeRoot = TreeNode(root)
                        treeRoot.left = leftTree
                        # 克隆右子树并且加上偏差
                        treeRoot.right = self.clone(rightTree, root)
                        dp[len].append(treeRoot)
        return dp[n]


class BinarySearchTree:
    # 递归 中序遍历，左子树---> 根结点 ---> 右子树。
    def InOder(self, root):
        """
        In-Order Traversal of binary tree
        :param root: root node of target binary tree
        :return: TreeNode
        """
        if not root:  return []  # 空节点
        res = [root.val]
        left_tree = self.InOder(root.left)
        right_tree = self.InOder(root.right)
        return left_tree + res + right_tree

    # 广度优先遍历(基于队列/循环)
    def BreadthOrder(self, root):
        """
        Breadth-first-Order Traversal of binary tree based on circulation
        :param root: root node of target binary tree
        :return: TreeNode
        """
        queue = []
        res = []
        queue = []
        # 入队 queue.append(i)
        # 出队 queue[0] queue[1:] 或者 queue.pop()
        # root inQueue 对象入队
        queue.append(root)
        # 然后就循环出队root，root.left节点入队（先入先出），root.right节点再入队（后入后出），直到队列为空，结束循环。
        while len(queue):
            t = queue.pop(0)
            # 不处理None模式的5行代码
            # if t == None:
            #     continue
            # queue.append(t.left)
            # queue.append(t.right)
            # res.append(t.val)
            # 处理None模式的6行代码
            if t == None:
                res.append(None)  # 空节点也放进去
            else:
                queue.append(t.left)
                queue.append(t.right)
                res.append(t.val)
        return res


Input = [3]
Answer = [5]
if __name__ == "__main__":
    solution = Solution()
    BSTree = BinarySearchTree()
    for i in range(len(Input)): 
        print("-"*50)
        result = solution.generateTrees (Input[i])
        for treenode in result:
            print(BSTree.BreadthOrder(treenode))
  • 回溯算法的实现 最简洁的实现，推荐！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def generateTrees(self, n: int) -> List[TreeNode]:
        if n == 0: return []
        return self.dfs(1, n)
        
    def dfs(self, start, end):
        if start > end: return [None]
        res = []
        for rootval in range(start, end+1):
            LeftTree = self.dfs(start, rootval-1)
            RightTree = self.dfs(rootval+1, end)
            for i in LeftTree:
                for j in RightTree:
                    root = TreeNode(rootval)
                    root.left = i
                    root.right = j
                    res.append(root)
        return res

递归方法的实现

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
class Solution:
    def generateTrees(self, n):
        """
        :type n: int
        :rtype: List[TreeNode]
        """
        def generate_trees(start, end):
            if start > end:
                return [None,]
            
            all_trees = []
            for i in range(start, end + 1):  # pick up a root
                # all possible left subtrees if i is choosen to be a root
                left_trees = generate_trees(start, i - 1)
                
                # all possible right subtrees if i is choosen to be a root
                right_trees = generate_trees(i + 1, end)
                
                # connect left and right subtrees to the root i
                for l in left_trees:
                    for r in right_trees:
                        current_tree = TreeNode(i)
                        current_tree.left = l
                        current_tree.right = r
                        all_trees.append(current_tree)
            
            return all_trees
        
        return generate_trees(1, n) if n else []

时间复杂度 : 主要的计算开销在于构建给定根的全部可能树，也就是卡特兰数 \(G_n\)。该过程重复了 \(n\) 次，也就是 \(nG_n\)。卡特兰数以 \(\frac{4^n}{n^{3/2}}\) 增长。因此，总的时间复杂度为 \(O(\frac{4^n}{n^{1/2}})\)。这看上去很大，但别忘了，我们可是要生成 \(G_n\sim\frac{4^n}{n^{3/2}}\) 棵树的。

空间复杂度: \(G_n\) 棵树，每个有 \(n\) 个元素，共计 \(nG_n\)，也就是 \(O(\frac{4^n}{n^{1/2}})\)。

参考链接

力扣（LeetCode）windliang
LeetCode官方题解
九章算法