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 Queuedef preorder(root):&nbsp; &nbsp; ans = []&nbsp; &nbsp; q = Queue()&nbsp; &nbsp; q.put(root)&nbsp; &nbsp; while not q.empty():&nbsp; &nbsp; &nbsp; &nbsp; temp = []&nbsp; &nbsp; &nbsp; &nbsp; n = q.qsize()&nbsp; &nbsp; &nbsp; &nbsp; while n:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x = q.get()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n-=1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; temp.append(x.data)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if x.left:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.put(x.left)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if x.right:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; q.put(x.right)&nbsp; &nbsp; &nbsp; &nbsp; ans.append(temp)&nbsp; &nbsp; print(ans[::-1])&nbsp; &nbsp;# prints [[1], [2], [3, 5], [4]] for your example

Answer 2

我（终于）解决了这个问题，在尝试了 5 个小时的不同解决方案后，我回到了这个问题并纠正了它。这是正确的代码：import bstdef preorder(root, level, dict):&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # base case: empty tree&nbsp; &nbsp; &nbsp; &nbsp; if root is None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # insert current node and its level into the dict&nbsp; &nbsp; &nbsp; &nbsp; dict.setdefault(level, []).append(root.data)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # recur for left and right subtree by increasing level by 1&nbsp; &nbsp; &nbsp; &nbsp; if root.left is not None:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; preorder(root.left, level + 1, dict)&nbsp; &nbsp; &nbsp; &nbsp; if root.right is not None:&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; preorder(root.right , level + 1, dict)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # Recursive function to do reverse level order traversal of given binary treedef tree_levels(tree):&nbsp; &nbsp; &nbsp; &nbsp; list = []&nbsp; &nbsp; &nbsp; &nbsp; # create an empty dict to store nodes between given levels&nbsp; &nbsp; &nbsp; &nbsp; dict = {}&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # traverse the tree and insert its nodes into the dict&nbsp; &nbsp; &nbsp; &nbsp; # corresponding to the their level&nbsp; &nbsp; &nbsp; &nbsp; preorder(tree, 0, dict)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # iterate through the dict in reverse order and&nbsp; &nbsp; &nbsp; &nbsp; # print all nodes present in very level&nbsp; &nbsp; &nbsp; &nbsp; for i in range(len(dict)-1,-1,-1):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; list += dict[i]&nbsp; &nbsp; &nbsp; &nbsp; return list