我真的需要你幫助完成這個(gè)有關(guān)二叉搜索樹(shù)的練習(xí)。我必須一路顛倒從下到上、從左到右的遍歷順序。這是練習(xí)：給定 BST，編寫(xiě)一個(gè)返回值列表的函數(shù)。樹(shù)最后深度的元素將首先出現(xiàn)在輸出列表中。接下來(lái)將出現(xiàn)前一深度級(jí)別的元素，一直到根。相同深度的元素將按照從小到大的順序出現(xiàn)在列表中。elements_in_bst_by order(tree_node)# 返回一個(gè)列表例如，如果我們使用按以下順序插入的值2、1、3、0創(chuàng)建 BST ，則將返回此列表[0, 1, 3, 2]如果你不明白我會(huì)這樣解釋： 2 root level 0
1 3 children level 1
0 children level 2這應(yīng)該返回 0 然后 1 然后 3 然后最后 2 （根）這是練習(xí)中給出的模塊（它包含二叉搜索樹(shù)代碼，PS：必須使用此模塊）：class TreeNode(object): """A tree node with two children trees""" def __init__(self, data, parent=None, left=None, right=None): self.data = data self.parent = parent self.left = left self.right = right def search(self, value): """Search in a BST""" if self.data is None: return None if self.data == value: return self if value < self.data: if self.left is None: return None return self.left.search(value) else: if self.right is None: return None return self.right.search(value) def insert(self, value): """insert a node in a BST""" if self.data is None: self.data = value return if value < self.data: if self.left is None: self.left = TreeNode(value, self) else: self.left.insert(value) else: if self.right is None: self.right = TreeNode(value, self) else: self.right.insert(value)它給了我這個(gè)錯(cuò)誤：列表不同： [2,1] != [1,2]預(yù)期：[2,1]實(shí)際：[1,2]
2 回答
臨摹微笑
TA貢獻(xiàn)1982條經(jīng)驗(yàn) 獲得超2個(gè)贊
只需使用隊(duì)列創(chuàng)建一個(gè)簡(jiǎn)單的前序遍歷即可。
from queue import Queue
def preorder(root):
ans = []
q = Queue()
q.put(root)
while not q.empty():
temp = []
n = q.qsize()
while n:
x = q.get()
n-=1
temp.append(x.data)
if x.left:
q.put(x.left)
if x.right:
q.put(x.right)
ans.append(temp)
print(ans[::-1]) # prints [[1], [2], [3, 5], [4]] for your example
富國(guó)滬深
TA貢獻(xiàn)1790條經(jīng)驗(yàn) 獲得超9個(gè)贊
我（終于）解決了這個(gè)問(wèn)題，在嘗試了 5 個(gè)小時(shí)的不同解決方案后，我回到了這個(gè)問(wèn)題并糾正了它。這是正確的代碼：
import bst
def preorder(root, level, dict):
# base case: empty tree
if root is None:
return
# insert current node and its level into the dict
dict.setdefault(level, []).append(root.data)
# recur for left and right subtree by increasing level by 1
if root.left is not None:
preorder(root.left, level + 1, dict)
if root.right is not None:
preorder(root.right , level + 1, dict)
# Recursive function to do reverse level order traversal of given binary tree
def tree_levels(tree):
list = []
# create an empty dict to store nodes between given levels
dict = {}
# traverse the tree and insert its nodes into the dict
# corresponding to the their level
preorder(tree, 0, dict)
# iterate through the dict in reverse order and
# print all nodes present in very level
for i in range(len(dict)-1,-1,-1):
list += dict[i]
return list
添加回答
舉報(bào)
0/150
提交
取消