這篇文章主要講解了“怎么使用Java遞歸推出給定節點數的所有形狀二叉搜索樹”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“怎么使用Java遞歸推出給定節點數的所有形狀二叉搜索樹”吧！

樂都網站制作公司哪家好，找創新互聯建站！從網頁設計、網站建設、微信開發、APP開發、自適應網站建設等網站項目制作，到程序開發，運營維護。創新互聯建站從2013年創立到現在10年的時間，我們擁有了豐富的建站經驗和運維經驗，來保證我們的工作的順利進行。專注于網站建設就選創新互聯建站。

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

文章名稱：怎么使用Java遞歸推出給定節點數的所有形狀二叉搜索樹
分享地址：http://www.yijiale78.com/article8/pehgip.html

成都網站建設公司_創新互聯，為您提供網站策劃、品牌網站設計、服務器托管、App開發、手機網站建設、移動網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯