叶到根的 bst 遍历

Question

我只是想知道，给定一个指向其左侧和右侧的节点 children，是否有可能以某种方式获得整个 bst 树的有序打印？

关于这棵树，我只知道它是 BST。 而我对节点的了解就是他知道他的 children 是谁（左和右）。 我无权访问节点的根节点和父节点。 选择的节点是随机选择的，我需要return整棵树的顺序。

我认为没有足够的信息可以开始，我的朋友在求职面试中遇到了这个问题，想知道这是一个无法解决的问题还是有我不知道的技巧？

提前感谢您的帮助:)

Answer 1

在这种情况下你唯一能做的就是向下移动，因为你没有指向父节点的指针。可以打印整棵树的唯一情况是所考虑的节点是根节点。

因此，您可以获得以当前节点为根的子树的顺序打印。如果这个节点是根，那么它会打印整棵树。如果不是，那就不是。

以防万一，顺序打印很简单：

def inorder(node):
    if node == null: return
    inorder(node.left)
    print node.data
    inorder(node.right)