怎么使用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遞歸推出給定節點數的所有形狀二叉搜索樹這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！