1回答

liuyubobobo

2023-01-11

已采纳

中序遍历恢复 BST，第一步就会出问题。

如果是前序遍历恢复 BST，我们可以肯定，整个序列的第一个节点一定是根节点。我们据此，根据 BST 的性质，就可以继续构建整个 BST。

如果是后续遍历恢复 BST，我们可以肯定，整个序列的最后一个节点一定是根节点。我们据此，根据 BST 的性质，就可以继续构建整个 BST。

但是对于中序遍历，整个序列中的任何一个节点，都可以是根节点。

==========

比如中序遍历是 1，2，3 的 BST，下面三棵树分别是以 1， 2， 3 为根的，中序遍历为 1，2，3 的 BST

// 以 1 为根节点
1
 \
  2
   \
    3

// 以 2 为根节点
  2
 / \
1   3

// 以 3 为根节点
    3
   / 
  2   
 /
1

继续加油！：）

0