binary-tree - 绘制给定“ATTA”的二叉树作为中序和后序遍历

Question

我被要求绘制一个二叉搜索树，它的顺序和后序遍历都按顺序处理节点"ATTA"。我尝试了许多不同的方法，但最终只适用于其中一种遍历方法。

Answer 1

我相信您只是在谈论常规的二叉树，因为创建这样的二叉搜索树是不可能的。

鉴于后序以 结尾A，我们知道根必须是A。

假设我们只有 2A的顺序，并且根是A，我们知道根的左子树或右子树是空的。

鉴于后序中的倒数第二个节点是 a T，我们知道根的孩子必须是 a T。

从这里我们可以检查剩下的 4 种可能性：

               A        A    A        A
              /        /      \        \
             T        T        T        T
            / \      / \      / \      / \
           A   T    T   A    A   T    T   A

Inorder     ATTA     TTAA     ATAT     ATTA
Postorder   ATTA     TATA     ATTA     TATA

所以唯一的可能是：

    A
   /
  T
 / \
A   T

...这不是二叉搜索树。