這篇文章主要講解了“怎么使用Java遞歸推出給定節(jié)點數(shù)的所有形狀二叉搜索樹”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“怎么使用Java遞歸推出給定節(jié)點數(shù)的所有形狀二叉搜索樹”吧！
題目：給定節(jié)點，比如3，三個節(jié)點；返回一個隊列，包括所有形狀二叉搜索樹（Binary Search Trees)。具體如下圖。
給出三個點，返回三個節(jié)點組成不同形狀的樹。我當(dāng)時看的時候沒有注意到是二叉搜索樹（BST)，以為是任意二叉樹，走了彎路。
這里先說下二叉搜索樹，，所謂二叉搜索樹，其實就是對于一棵二叉樹，不存在重復(fù)值節(jié)點，任意節(jié)點的左節(jié)點的值小于父節(jié)點，右節(jié)點大于其父節(jié)點。主要為了搜索方便，這樣就可以通過大小對比，只有sqrt(n)的速度搜索到某個給定值的節(jié)點。使用中序遍歷二叉搜索樹，可以得到一個順序數(shù)列。
因為一開始沒有注意到是二叉搜索樹，所以就簡單用普通二叉樹的思路。
- 使用遞歸，求n個節(jié)點的形狀隊列，是把n-1個節(jié)點形狀隊列的每個樹，可能增加的地方，增加一個節(jié)點，
- 可能存在增加后，圖形相同的樹，這時候使用序列化，把樹存儲一個字符串，并替換節(jié)點值為1；如果字符串相同，就是相同圖形的樹；這里使用字典來存儲，把序列化的字符串作為key鍵值；因為字典的key鍵值是唯一，可以用來過濾重復(fù)樹。
- 這個時候提交代碼，發(fā)現(xiàn)不通過，才發(fā)現(xiàn)要二叉搜索樹，不想改思路了，就定義一個方法，中序遍歷那些已經(jīng)算出來的樹隊列，按照中序遍歷順序賦值。
- 提交通過，不過效率太低了。學(xué)習(xí)了下，使用動態(tài)規(guī)劃（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遞歸推出給定節(jié)點數(shù)的所有形狀二叉搜索樹”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對怎么使用Java遞歸推出給定節(jié)點數(shù)的所有形狀二叉搜索樹這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！
