怎么使用Java递归推出给定节点数的所有形状二叉搜索树

这篇文章主要讲解了“怎么使用Java递归推出给定节点数的所有形状二叉搜索树”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“怎么使用Java递归推出给定节点数的所有形状二叉搜索树”吧！

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

给出三个点，返回三个节点组成不同形状的树。我当时看的时候没有注意到是二叉搜索树（BST)，以为是任意二叉树，走了弯路。

这里先说下二叉搜索树，，所谓二叉搜索树，其实就是对于一棵二叉树，不存在重复值节点，任意节点的左节点的值小于父节点，右节点大于其父节点。主要为了搜索方便，这样就可以通过大小对比，只有sqrt(n)的速度搜索到某个给定值的节点。使用中序遍历二叉搜索树，可以得到一个顺序数列。

因为一开始没有注意到是二叉搜索树，所以就简单用普通二叉树的思路。

- 使用递归，求n个节点的形状队列，是把n-1个节点形状队列的每个树，可能增加的地方，增加一个节点，

- 可能存在增加后，图形相同的树，这时候使用序列化，把树存储一个字符串，并替换节点值为1；如果字符串相同，就是相同图形的树；这里使用字典来存储，把序列化的字符串作为key键值；因为字典的key键值是唯一，可以用来过滤重复树。

- 这个时候提交代码，发现不通过，才发现要二叉搜索树，不想改思路了，就定义一个方法，中序遍历那些已经算出来的树队列，按照中序遍历顺序赋值。

- 提交通过，不过效率太低了。学习了下，使用动态规划（Dynamical Plan) 才是明路，后面会再写一个DP方法的。

代码如下，也算是一个反面教材。

另外这个地方还有一个注意点，就是深度拷贝，因为每个唯一图形树都要保存，所以保存时候用深度拷贝。

# 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 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 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

感谢各位的阅读，以上就是“怎么使用Java递归推出给定节点数的所有形状二叉搜索树”的内容了，经过本文的学习后，相信大家对怎么使用Java递归推出给定节点数的所有形状二叉搜索树这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是亿速云，小编将为大家推送更多相关知识点的文章，欢迎关注！