BST（二叉搜索树）反向层序遍历没有给我正确的 answer/result

Question

我真的需要你的帮助来完成这个关于二叉搜索树的练习。一路上我要把遍历的顺序从下向上，从左到右倒过来。这是练习：

Given a BST, write a function that will return a list of values. Elements at the last depth of the tree will appear first in the output list. The elements at the previous depth level will appear next, all the way to the root. Elements at the same depth will appear in the list from smallest to largest.

elements_in_bst_by order(tree_node)# returns a list

For example, if we created a BST using the values inserted in the following order 2, 1, 3, 0 would return this list [0, 1, 3, 2]

如果你不明白我会这样解释：

            2          root level 0
          1   3        children level 1
        0              children level 2

this should return 0 then 1 then 3 then finally 2 (root)

这是练习中给出的模块（它包含二叉搜索树代码，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)

这是我的代码：

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(0,len(dict)):
        list.append(dict[i])
    newest = [i[0] for i in list]
    return newest
root = TreeNode(4)
root.insert(5)
root.insert(3)
root.insert(2)
root.insert(1)
tree_levels(root)

它给我这个错误：

list differ: [2,1] != [1,2]

Expected: [2,1]

Actual: [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

BST（二叉搜索树）反向层序遍历没有给我正确的 answer/result

BST (Binary Search Tree) reverse level-order traversal isn't giving me the correct answer/result

python

python-3.x

binary-search-tree