按顺序遍历 BST 并将节点存储在数组中，但输出未排序？

Question

我正在遍历 in-order manner 中的 Binary Tree 以确定它是否是 Binary Search Tree。这是我的代码：

class T:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def is_bst(node):  
    if not node:
        return 

    output = []
    
    is_bst(node.left)
    output.append(node.value) 
    is_bst(node.right)
    print(output)

对于上面的例子，output = [1,3,2,9,7,5]

但这显然是不正确的！ - 我通常会调试，但我不熟悉运行 trees/binary 树作为输入。知道我的代码哪里出错了吗？？？

更新代码：

class T:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

        
def inOrderTraversal(node,output): 
        if not node: 
            return None
        
        is_bst(node.left)
        output.append(node.value) 
        is_bst(node.right)
        return 
    
def is_bst(node):  
    
    output = []
    
    inOrderTraversal(node,output)
    
    print(output)

同样的例子，output = [1,3,2,9,7,5]还是错的

Answer 1

您在例程中创建 output，因此它始终是空的。然后添加当前节点的值，但在例程结束时打印它。结果是 postorder，而不是 inorder - 每个节点都在 after 它的两个子树中打印。

除了代码结构之外，您的函数名称错误 - 您实际上不希望它回答树是否为 BST，您只希望它return 内容：

def dump_tree_inorder(node, output):  
    if not node:
        return 
    
    dump_tree_inorder(node.left, output)
    output.append(node.value) 
    dump_tree_inorder(node.right, output)

按顺序遍历 BST 并将节点存储在数组中，但输出未排序？

Traversing a BST in an in-order fashion and storing the nodes in an array, but the output is not sorted?

python

binary-tree