BST（二叉搜索树）反向层序遍历没有给我正确的答案/结果

Question

我真的需要你帮助完成这个有关二叉搜索树的练习。我必须一路颠倒从下到上、从左到右的遍历顺序。这是练习：给定 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]

Answer 1

只需使用队列创建一个简单的前序遍历即可。

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

Answer 2

我（终于）解决了这个问题，在尝试了 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