tree - 使用中序和前序遍历生成二叉树

Question

我想使用以下中序/前序遍历生成二叉树；

顺序 = 卧龙岗

预购 = GLOWOLNNGO

这是我想出的树：

       G
      /  \
     L    N
    / \  /  \
   O  O  O   G
  /  / \   
 W  L   N 

它适用于中序遍历，但不满足前置条件。由于重复的字母，我发现它令人困惑。

我的猜测是我使用了错误的“G”作为根？

提前致谢！

标签： treebinary-treeinorderpreorder

Answer 1

实际上，前序的第一个 G 恰好对应于中序中的最后一个 G，即根没有右子树。这将适合：

         G
        /
       L
      / \
     O   O
    /   / \
   W   L   N
            \
             N
            /
           G
            \
             O