c - 按顺序定位存储在数组中的二叉树中的根节点

Question

示例树

2 -> root
1 -> Left
3 -> right 

按[1, 2, 3]顺序存储在数组中

知道树是有序存储的，如何检索根节点？

根据我的说法，这三个都是根节点的可能候选者。

Answer 1

事实上，所有 3 个都是可能的候选人。

以下是可能导致给定中序遍历的树:

 1           2           3
  \         / \         /
   2       1   3       2
    \                 /
     3               1

中序遍历不一定足以唯一标识一棵树(因此始终标识根)。假设树元素唯一，您需要先序遍历或后序遍历与中序遍历配对。

引用 - Which combinations of pre-, post- and in-order sequentialisation are unique?