search - 用前序和中序遍历重构二叉搜索树

Question

我正在研究一个重建二叉搜索树的函数。我试着先用手做。

说我有：pre- 10,3,5,4,15,7,8,2,9,20 in- 4,5,3,15,10,20,8,7,9,20

我想不通。我知道 10 必须是根，并且有序序列中 10 左侧的所有数字都需要在右子树中。

那会给我 4,5,3,15

15 大于 10 并且要成为二叉搜索树，左子树中的所有节点都应该小于根。

这是否意味着这两个序列形成了无效的二叉搜索树？

Answer 1

你是对的。根据您获得的按顺序遍历，您的树似乎不是 BST。10 必须是根节点，正如您从前序遍历中的第一个节点中收集到的那样。有序遍历中 10 左边的所有内容都应该在左子树中，而 10 右边的所有内容都应该在右子树中。正如您所指出的，15 不可能在 10 的左侧（或者 7、8 和 9 不可能在 10 的右侧）。话虽如此，您仍然可以从这些数据中重建一棵树。它只是没有按排序顺序排列的节点。