使用递归推出给定节点数的所有形状二叉搜索树(Binary Search Trees)

这道题倒是花了不少时间,主要问题是审题不清哈。

 

题目:给定节点,比如3,三个节点;返回一个队列,包括所有形状二叉搜索树(Binary Search Trees)。具体如下图。

使用递归推出给定节点数的所有形状二叉搜索树(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 = None import copy class 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 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 sortTree def 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
上一篇:HP-JavaUtil: xls 操作类


下一篇:集合和String