仅通过中序遍历结果能否构造出对应的二叉搜索树(BST)？

核心结论 #

仅通过有序的中序遍历结果，无法构造出唯一的二叉搜索树（BST）。
因为BST的中序遍历天然就是有序序列，同一个有序中序序列可以对应无数种结构不同的BST。举个简单例子：中序序列[1,2,3]至少可以对应以下3种完全不同的BST：

1. 根节点为2，左子节点为1，右子节点为3（平衡BST）
2. 根节点为1，右子节点为2，2的右子节点为3（右斜树）
3. 根节点为3，左子节点为2，2的左子节点为1（左斜树）

构造任意一个符合要求的BST的递归方案 #

如果你不需要唯一结构，只需要得到任意一个满足中序遍历要求的BST，最常用的是构造平衡BST，递归实现逻辑非常清晰：

• 处理当前区间的中序序列时，取区间中点的元素作为根节点
• 中点左侧的子序列递归构造为根的左子树
• 中点右侧的子序列递归构造为根的右子树

示例Python代码 #

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def build_bst(nums):
    def dfs(left, right):
        if left > right:
            return None
        # 取中间节点作为根，保证树平衡
        mid = (left + right) // 2
        root = TreeNode(nums[mid])
        root.left = dfs(left, mid - 1)
        root.right = dfs(mid + 1, right)
        return root
    return dfs(0, len(nums) - 1)

构造所有符合要求的BST的递归方案 #

如果你需要得到所有可能的BST结构，递归逻辑如下：

• 遍历当前区间的每一个位置i，将nums[i]作为根节点
• 递归生成左侧区间所有可能的左子树集合left_trees
• 递归生成右侧区间所有可能的右子树集合right_trees
• 遍历所有左、右子树的组合，拼接到当前根节点上，收集所有可能的根节点作为当前区间的结果集合

补充说明 #

如果需要得到唯一的BST结构，必须额外补充约束条件，比如要求BST为平衡树、完全二叉树，或者额外提供前序/后序/层序遍历结果，仅靠中序遍历无法确定唯一结构。

内容的提问来源于stack exchange，提问作者user496934