从前序遍历列表Python构造完整的二叉树

Question

如何仅使用内置列表从Python中的预订单列表构建二叉树（非二叉搜索树）？预订单列表中的每个节点还有一个“标志”，显示它是叶子还是内部节点。每个节点有2个孩子（0号或1号孩子）

我创建了一个代表Node的类

class Node:
    def __init__(self, initType):
        self.type = initType
        self.leftChild = None
        self.rightChild = None

我想我应该在这里使用stack，但我不想import stack库。

我在网上找到的解决方案仅适用于BST，或者输入包含订单列表和预订单列表，而不仅仅是预订单列表。

Answer 1

只有预订遍历才能唯一地重新创建二叉树。这就是为什么您在网上找到的解决方案是针对BST的，或者也提供了订单列表。

例如，如果预订单列表为[1,2,3]

那么你原来的二叉树可能是：

         1
       /
     2
   /
  3

或者可能是：

1
  \
   2
    \
     3 

**注意它们是不同的树，但是会有相同的预订遍历列表！

如果在一次采访中询问了这个问题，那就意味着你是否会注意到一个独特的二叉树无法实现这一事实并让你澄清一个问题：“二叉树是二元搜索树吗？”

在访谈中很常见的是从问题中遗漏事实让你提出问题。