怎么使用Java遞歸推出給定節(jié)點(diǎn)數(shù)的所有形狀二叉搜索樹

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

題目：給定節(jié)點(diǎn)，比如3，三個節(jié)點(diǎn)；返回一個隊列，包括所有形狀二叉搜索樹（Binary Search Trees)。具體如下圖。

給出三個點(diǎn)，返回三個節(jié)點(diǎn)組成不同形狀的樹。我當(dāng)時看的時候沒有注意到是二叉搜索樹（BST)，以為是任意二叉樹，走了彎路。

這里先說下二叉搜索樹，，所謂二叉搜索樹，其實(shí)就是對于一棵二叉樹，不存在重復(fù)值節(jié)點(diǎn)，任意節(jié)點(diǎn)的左節(jié)點(diǎn)的值小于父節(jié)點(diǎn)，右節(jié)點(diǎn)大于其父節(jié)點(diǎn)。主要為了搜索方便，這樣就可以通過大小對比，只有sqrt(n)的速度搜索到某個給定值的節(jié)點(diǎn)。使用中序遍歷二叉搜索樹，可以得到一個順序數(shù)列。

因為一開始沒有注意到是二叉搜索樹，所以就簡單用普通二叉樹的思路。

- 使用遞歸，求n個節(jié)點(diǎn)的形狀隊列，是把n-1個節(jié)點(diǎn)形狀隊列的每個樹，可能增加的地方，增加一個節(jié)點(diǎn)，

- 可能存在增加后，圖形相同的樹，這時候使用序列化，把樹存儲一個字符串，并替換節(jié)點(diǎn)值為1；如果字符串相同，就是相同圖形的樹；這里使用字典來存儲，把序列化的字符串作為key鍵值；因為字典的key鍵值是唯一，可以用來過濾重復(fù)樹。

- 這個時候提交代碼，發(fā)現(xiàn)不通過，才發(fā)現(xiàn)要二叉搜索樹，不想改思路了，就定義一個方法，中序遍歷那些已經(jīng)算出來的樹隊列，按照中序遍歷順序賦值。

- 提交通過，不過效率太低了。學(xué)習(xí)了下，使用動態(tài)規(guī)劃（Dynamical Plan) 才是明路，后面會再寫一個DP方法的。

代碼如下，也算是一個反面教材。

另外這個地方還有一個注意點(diǎn)，就是深度拷貝，因為每個唯一圖形樹都要保存，所以保存時候用深度拷貝。

# 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遞歸推出給定節(jié)點(diǎn)數(shù)的所有形狀二叉搜索樹”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對怎么使用Java遞歸推出給定節(jié)點(diǎn)數(shù)的所有形狀二叉搜索樹這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！