证明或反驳：如果你得到了一个二叉搜索树的前序遍历，你可以唯一确定那个二叉搜索树

Question

这是我从旧考试中找到的任务，我尝试解决它，因为他们可以在星期五为我提出类似的问题。

对于解决方案，我有便宜的解决方案，但我认为二叉搜索树的定义很重要。

我做了第一棵树：

1
 \
  1
   \
    1

这是第二棵树

    1
   /
  1
 /
1

当你进行预序遍历时，你对两棵树都有相同的输出..因为相同的元素，并且都有退化树。但是你没有同一棵树！所以说法是错误的。

唯一的问题是我的树是二叉搜索树...我想是的，因为二叉搜索树的元素可以有更大/更小的相等元素？

当我问我们老师时请停下来他说我可以在假期结束时问他但是假期结束后我的考试就结束了....对我来说没什么好事。

Answer 1

考虑到 BST 的标准定义，您的回答完全正确。根据标准定义，BST 可以有重复的元素，相同的元素可以进入任一子树。

如果问题针对的是没有重复项的情况，或者重复项必须仅存在于左（或仅右）子树中，则前序遍历足以重建树。

如果不允许重复，则递归构建树：以根为第一个节点，然后以原遍历中节点数小于(for左子树）和大于（对于右子树）根节点。如果允许重复但被限制在左子树或右子树中，则使用相同的过程，但将 "or equal" 添加到小于或大于，但不能同时添加。