已知二叉搜索树前序遍历序列，求后序遍历序列及树结构

核心依据 #

二叉搜索树（BST）的核心性质：任意节点的左子树所有节点值均小于该节点值，右子树所有节点值均大于该节点值；前序遍历顺序为根节点 → 左子树 → 右子树。

逐步推导树结构 #

已知前序序列：15, 9, 6, 1, 7, 13, 23, 19, 39, 32

1. 第一层（根节点）

   • 前序第一个元素15是整棵树的根。
   • 划分左右子树：找到第一个大于15的元素23，因此：
     • 左子树前序序列：9, 6, 1, 7, 13
     • 右子树前序序列：23, 19, 39, 32

2. 左子树（根为9）

   • 前序第一个元素9是左子树的根。
   • 划分左右子树：找到第一个大于9的元素13，因此：
     • 左子树的左子树序列：6, 1, 7
     • 左子树的右子树序列：13（仅一个节点，直接作为9的右孩子）

3. 左子树的左子树（根为6）

   • 前序第一个元素6是该子树的根。
   • 划分左右子树：找到第一个大于6的元素7，因此：
     • 该子树的左子树序列：1（仅一个节点，作为6的左孩子）
     • 该子树的右子树序列：7（仅一个节点，作为6的右孩子）

4. 右子树（根为23）

   • 前序第一个元素23是右子树的根。
   • 划分左右子树：找到第一个大于23的元素39，因此：
     • 右子树的左子树序列：19（仅一个节点，作为23的左孩子）
     • 右子树的右子树序列：39, 32

5. 右子树的右子树（根为39）

   • 前序第一个元素39是该子树的根。
   • 划分左右子树：所有剩余元素32均小于39，因此32作为39的左孩子，无右子树。

最终后序遍历序列 #

后序遍历顺序为左子树 → 右子树 → 根节点，按照上述结构推导，后序序列为：
1, 7, 6, 13, 9, 19, 32, 39, 23, 15

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