可以证明，从先序遍历（或后序遍历）中可以唯一地重建一棵二叉搜索树。

Question

可以证明，从先序遍历（或后序遍历）中可以唯一地重建一棵二叉搜索树。

3

对于二叉搜索树，先序遍历或后序遍历足以明确地重建其原始二叉搜索树。但我找不到证明或解释为什么会这样。对于中序遍历，很容易想出一个反例来显示可能有许多不同的BST与给定的中序遍历相对应。是否有任何证明或参考资料表明先序遍历或后序遍历足以明确地重建其原始BST？这是针对BST而不是一般的二叉树。

- SHH

2

考虑前序遍历从根开始，然后是左子树，接着是右子树。因此第一个元素肯定是根。是否有可能在剩余的遍历中选择左子树结束和右子树开始的位置有多种方式？如果没有这样的歧义-可以确定唯一点，那么只有一种选择根、左子树节点和右子树节点的方法。每个子树都是BST，因此如果您可以像这样唯一地拆分整个树，则可以使用子树进行操作。 - moreON

3

如果不允许有重复的元素，moreON的观点是正确的。但如果允许有重复的元素，则该说法是错误的：1 1 1 是5个不同BST的先序遍历序列。 - ruakh

@ruakh - 如果你仔细阅读，你会发现我提出了一种方法来推理这个问题，你可以在其中放置自己的规则和关于BST的假设，从而得出适当的结论，而不是为任何特定的结论构造一个具体的论点。请注意使用“如果…”来允许人们得出自己的结论。我承认，在评论中所需的简洁性肯定会引导读者朝着一组假设的方向。 - moreON

1

@moreON：我的评论并不是针对你的批评；如果让你误解了，我很抱歉。OP正在寻求证明某个主张，只要这个主张是正确的，你的证明（即你的评论所引导OP的证明）就是正确的。我只是指出了主张中的一些模糊之处，并澄清只有在一种解释下它才是正确的。 - ruakh

请自行将其转换为值得回答的内容，并声称您的正确答案奖金，我没有任何抱怨。我认为现在它可能还不足以成为一个答案。 - moreON

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Abhishek Kumar · Accepted Answer

根据前序遍历的定义，保证根节点是第一个元素。

现在，假设有一组唯一的元素将出现在根节点左半部分 - 即所有值小于root->val的元素。

同样适用于右子树。

现在，我们必须递归地应用上述逻辑到左子树和右子树。

由于后序遍历只是反向树上的前序遍历，因此相同的逻辑也适用于后序遍历。