这道题倒是花了不少时间，主要问题是审题不清哈。
题目：给定节点，比如3，三个节点；返回一个队列，包括所有形状二叉搜索树（Binary Search Trees)。具体如下图。
给出三个点，返回三个节点组成不同形状的树。我当时看的时候没有注意到是二叉搜索树（BST)，以为是任意二叉树，走了弯路。
这里先说下二叉搜索树，，所谓二叉搜索树，其实就是对于一棵二叉树，不存在重复值节点，任意节点的左节点的值小于父节点，右节点大于其父节点。主要为了搜索方便，这样就可以通过大小对比，只有sqrt(n)的速度搜索到某个给定值的节点。使用中序遍历二叉搜索树，可以得到一个顺序数列。
因为一开始没有注意到是二叉搜索树，所以就简单用普通二叉树的思路。
- 使用递归，求n个节点的形状队列，是把n-1个节点形状队列的每个树，可能增加的地方，增加一个节点，
- 可能存在增加后，图形相同的树，这时候使用序列化，把树存储一个字符串，并替换节点值为1；如果字符串相同，就是相同图形的树；这里使用字典来存储，把序列化的字符串作为key键值；因为字典的key键值是唯一，可以用来过滤重复树。
- 这个时候提交代码，发现不通过，才发现要二叉搜索树，不想改思路了，就定义一个方法，中序遍历那些已经算出来的树队列，按照中序遍历顺序赋值。
- 提交通过，不过效率太低了。学习了下，使用动态规划（Dynamical Plan) 才是明路，后面会再写一个DP方法的。
代码如下，也算是一个反面教材。
另外这个地方还有一个注意点，就是深度拷贝，因为每个唯一图形树都要保存，所以保存时候用深度拷贝。
|
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
|
# Definition for a binary tree node.# class TreeNode:# def __init__(self, x):# self.val = x# self.left = None# self.right = Noneimport copyclass Solution: cacheDict = {1:[TreeNode(‘x‘)]} def buildNewTree(self, Tree): nodelist = [Tree] NewTreeDict = {} while nodelist != []: templist = [] for node in nodelist: if node.left != None: templist.append(node.left) else: node.left = TreeNode(‘x‘) NewTreeDict[self.buildKey(Tree)] = (copy.deepcopy(Tree)) node.left = None if node.right != None: templist.append(node.right) else: node.right = TreeNode(‘x‘) NewTreeDict[self.buildKey(Tree)] = (copy.deepcopy(Tree)) node.right = None nodelist = templist return NewTreeDict def buildKey(self,Tree): Treekey = ‘‘ nodelist = [Tree] while nodelist !=[]: templist = [] for node in nodelist: if node.left != None: templist.append(node.left) Treekey = Treekey + ‘1‘ else: Treekey = Treekey + ‘0‘ if node.right != None: templist.append(node.right) Treekey = Treekey + ‘1‘ else: Treekey = Treekey + ‘0‘ nodelist = templist return Treekey def generateXTrees(self, n): if n in self.cacheDict.keys(): return self.cacheDict[n] else: TreeListDict = {} for Tree in self.generateXTrees(n-1): TreeListDict.update(self.buildNewTree(Tree)) self.cacheDict[n] = TreeListDict.values() return self.cacheDict[n] def generateTrees(self, n: int): sortTree = [] if n != 0: TreeList = self.generateXTrees(n) for tree in TreeList: sortTree.append(SortTheTree(copy.deepcopy(tree))) return sortTreedef SortTheTree(Tree): sortNum = 1 Treelist = [Tree] nodePoint = Tree while Treelist !=[] or nodePoint.val == ‘x‘: if nodePoint.left != None and nodePoint.left.val == ‘x‘: nodePoint = nodePoint.left Treelist.append(nodePoint) elif nodePoint.right != None and nodePoint.right.val == ‘x‘: if nodePoint.val == ‘x‘: nodePoint.val = sortNum sortNum = sortNum + 1 nodePoint = nodePoint.right Treelist.append(nodePoint) else: if nodePoint.val == ‘x‘: nodePoint.val = sortNum sortNum = sortNum + 1 if Treelist != []: nodePoint = Treelist.pop() return Tree |
使用递归推出给定节点数的所有形状二叉搜索树（Binary Search Trees）
原文：https://www.cnblogs.com/chenguopa/p/15239835.html