Shulou(Shulou.com)06/02 Report--

This article mainly explains how to use Java to recursively deduce all shapes of binary search trees with a given number of nodes. The content of the explanation in this article is simple and clear, and it is easy to learn and understand. Please follow Xiaobian's train of thought to study and learn how to use Java to recursively derive all shapes of binary search trees with a given number of nodes.

Topic: given nodes, such as 3, three nodes; return a queue, including all shape binary search trees (Binary Search Trees). The details are as follows.

Three points are given and three nodes are returned to form trees of different shapes. When I looked at it at that time, I didn't notice that it was a binary search tree (BST). I thought it was an arbitrary binary tree and took a detour.

Here we first talk about the next binary search tree, the so-called binary search tree, in fact, for a binary tree, there is no duplicate value node, the value of the left node of any node is less than the parent node, and the right node is larger than its parent node. It is mainly for the convenience of search, so that only the speed of sqrt (n) can search a node of a given value through size comparison. Using the middle order to traverse the binary search tree, you can get a sequential sequence.

Because I didn't notice that it was a binary search tree at first, I simply used the idea of an ordinary binary tree.

-use recursion to find the shape queue of n nodes, which is to add a node to each tree of the shape queue of 1 node.

-there may be a tree with the same graph after addition, so serialization is used to store a string in the tree and replace the node value to 1; if the string is the same, it is a tree with the same figure; here, a dictionary is used to store the serialized string as the key key value; because the key key value of the dictionary is unique, it can be used to filter duplicate trees.

-when you submit the code and find that it is not passed, you will find that you need a binary search tree. If you do not want to change your thinking, you will define a method to traverse the calculated tree queues in the middle order and assign values in the middle order.

-submitted and approved, but the efficiency is too low. After learning, the use of dynamic programming (Dynamical Plan) is the clear way, and a DP method will be written later.

The code is as follows, which is also a negative example.

There is another point to note in this place, that is, deep copy, because each unique graphic tree needs to be saved, so use deep copy when saving.

# 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') New TreeDict [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 Mel 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 = = 'Xerox: nodePoint = nodePoint.left Treelist.append (nodePoint) elif nodePoint.right! = None and nodePoint.right.val = =' Xerox: if nodePoint.val = = 'xcow: nodePoint.val = sortNum sortNum = sortNum + 1 nodePoint = nodePoint.right Treelist.append (nodePoint) Else: if nodePoint.val: nodePoint.val = sortNum sortNum = sortNum + 1 if Treelist! = []: nodePoint = Treelist.pop () return Tree Thank you for your reading The above is the content of "how to use Java to recursively derive all shapes of binary search trees with a given number of nodes". After the study of this article, I believe you have a deeper understanding of how to use Java to recursively derive all shapes of binary search trees with a given number of nodes, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.