如何根据后序遍历序列重建二叉树并正确推导先序遍历？

首先明确核心前提：仅靠后序遍历无法唯一确定普通二叉树的结构，必须结合中序遍历；如果是二叉搜索树（左子树节点全小于根，右子树全大于根），则可以通过后序序列唯一重建。从你的构建过程看，应该是默认按二叉搜索树处理，但节点划分和树结构构建有误。

你的错误点分析 #

你给出的后序序列是[3 2 1 6 5 4 9 11 10 8 7]，根节点取最后一个元素7是对的，但后续子树划分和节点放置错误：

• 根7的左子树节点应为所有小于7的元素：[3,2,1,6,5,4]，右子树是大于7的元素：[9,11,10,8]，这部分你是对的，但左子树内部构建错误。
• 左子树的根是4（后序最后一个元素），小于4的元素是[3,2,1]（左子树），大于4的是[6,5]（右子树），但你把3放在4的右子树，这不符合二叉搜索树规则（3<4，应属于4的左子树分支）。
• 元素5>4，应作为4的右子树根，而不是3的右子节点；6>5，应作为5的右子节点，而非左子节点。

正确的重建步骤（二叉搜索树场景） #

按后序遍历「左→右→根」的规则，结合二叉搜索树的大小关系，逐步拆分：

1. 根节点：7，左子树后序[3,2,1,6,5,4]，右子树后序[9,11,10,8]
2. 左子树根：4，左子树后序[3,2,1]，右子树后序[6,5]
   • 左子树的根：1，无左子树（无小于1的元素），右子树后序[3,2]
     • 该子树根：2，无左子树，右子树后序[3]→根3
   • 右子树的根：5，无左子树，右子树后序[6]→根6
3. 右子树根：8，无左子树（无小于8的元素），右子树后序[9,11,10]
   • 该子树根：10，左子树后序[9]→根9，右子树后序[11]→根11

最终正确的二叉树结构：

7
     /   \
    4     8
   / \     \
  1   5     10
   \   \   /  \
    2   6 9   11
     \
      3

正确的先序遍历结果 #

先序遍历规则是「根→左→右」，遍历结果为：
7 4 1 2 3 5 6 8 10 9 11

通用重建规则（普通二叉树） #

如果是普通二叉树，必须同时提供后序遍历+中序遍历才能唯一重建：

• 用后序找根，在中序中分割左、右子树的中序序列
• 再根据左、右子树的节点数量，拆分后序序列为左、右子树的后序序列
• 递归重复上述步骤构建树

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