PAT/A1135Is It A Red-Black Tree读取时直接build树的依据是什么？

[ijesonchen]

读取时直接将使用build函数数据插入BST。理论依据时什么呢？感觉二叉树的前序遍历不能保证树的唯一性，那么如何保证按照前序插入构造出来的BST一定是原始BST呢？如果不唯一，是否会影响后续红黑树的判定？
如果是确定的，能否提供一下相关的资料？谢谢。

[liuchuo]

没理解错的话，你的问题是“按照前序插入构造出来的BST一定是原始BST” BST的中序是所有结点从小到大的数字排列顺序，BST的前序也给出了，前序中序可以唯一确定一棵树，既然已经给了前序，那么根据这个前序序列的数字大小关系能够得到中序，所以如果按照build方法将小的放在左边，大的放在右边，那么保证了中序遍历的结果就是从小到大的顺序，前序是按照根左右顺序给出的结点，所以结点一个个插入的过程中也保证了这棵树的根、左、右是按照前序的顺序，前序中序已经保证，那么得到的树一定是原始的BST

[ijesonchen]

明白了。非常感谢。