这是我从旧考试中找到的任务，我尝试解决它，因为他们可以在星期五为我提出类似的问题。
对于解决方案，我有便宜的解决方案，但我认为二叉搜索树的定义很重要。
我做了第一棵树:
1
\
1
\
1
这是第二棵树
1
/
1
/
1
当你进行预序遍历时，两棵树都有相同的输出......因为相同的元素，并且都有退化树。但是你没有同一棵树!所以这个说法是错误的。
唯一的问题是我的树是二叉搜索树...我认为是的，因为二叉搜索树的元素可以有更大/更小的相等元素？
当我问我们的老师时请停下来，他说我可以在假期结束时问他，但是当假期结束时我的考试就结束了......对我来说没什么好事。
最佳答案
考虑到 BST 的标准定义，您的回答完全没问题。根据标准定义，BST 可以有重复的元素，相同的元素可以进入任一子树。
如果问题针对的是没有重复项的情况，或者重复项必须仅存在于左(或仅右)子树中，则前序遍历足以重建树。
如果不允许重复，递归构建树如下:以根为第一个节点，然后以递归的方式创建左子树和右子树，将原始遍历中节点小于的部分作为输入遍历(对于左子树) 并且大于(对于右子树)根节点。如果允许重复但被限制在左子树或右子树中，则使用相同的过程，但将“或等于”添加到小于或大于，但不是两者。
关于algorithm - 证明或反驳 : If you got pre-order traversal of a binary search tree, 你可以唯一确定那个二叉搜索树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46455892/