重建一棵二叉树需要多少次树遍历？

Question

重建一棵二叉树至少需要多少次树遍历（前序、中序、后序）。我很确定它是两个，但是我在解释原因时遇到了问题。我还要说的是，这 3 种类型的每种组合都可以进行重建。

如果有人能给我一个正确的解释就太好了；）。

Answer 1

如果你只有一次遍历（如中序），你无法重建一棵唯一的树。你可以举例说明。

假设一棵树的中序遍历为：ABC。然后可以有很多树可以从这个重建：

A               B                C
 \             /  \             /
  B           A    C           B
   \                          /
    C                        A

因此，需要2次遍历才能唯一地重建一棵树。