我真的需要你幫助完成這個有關二叉搜索樹的練習。我必須一路顛倒從下到上、從左到右的遍歷順序。這是練習：給定 BST，編寫一個返回值列表的函數。樹最后深度的元素將首先出現在輸出列表中。接下來將出現前一深度級別的元素，一直到根。相同深度的元素將按照從小到大的順序出現在列表中。elements_in_bst_by order(tree_node)# 返回一個列表例如，如果我們使用按以下順序插入的值2、1、3、0創建 BST ，則將返回此列表[0, 1, 3, 2]如果你不明白我會這樣解釋： 2 root level 0
1 3 children level 1
0 children level 2這應該返回 0 然后 1 然后 3 然后最后 2 （根）這是練習中給出的模塊（它包含二叉搜索樹代碼，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)它給了我這個錯誤：列表不同： [2,1] != [1,2]預期：[2,1]實際：[1,2]
2 回答
臨摹微笑
TA貢獻1982條經驗 獲得超2個贊
只需使用隊列創建一個簡單的前序遍歷即可。
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
富國滬深
TA貢獻1790條經驗 獲得超9個贊
我（終于）解決了這個問題，在嘗試了 5 個小時的不同解決方案后，我回到了這個問題并糾正了它。這是正確的代碼：
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
添加回答
舉報
0/150
提交
取消