1. 简介
在本篇文章中，我们将探讨如何通过深度优先遍历序列重建二叉树。我们会以一个具体的二叉树为例，展示重建过程，并分析哪些遍历组合可以唯一重建出一棵二叉树。
2. 可用于重建二叉树的遍历组合
我们知道，二叉树可以通过不同的深度优先遍历方式来表示。要唯一重建一棵二叉树，通常需要结合两种遍历方式，因为单一的遍历结果不足以确定树的结构。
以下三种组合可以用于重建：
✅ 中序 + 先序
✅ 中序 + 后序
✅ 先序 + 后序（仅限满二叉树）
⚠️ 注意：除非是满二叉树，否则无法仅凭先序和后序重建出唯一的二叉树。因为这两种遍历方式无法区分某个节点是左孩子还是右孩子。
3. 实例演示
我们以下图这棵二叉树为例进行讲解：
该树的三种遍历结果如下：
4. 从先序与中序重建二叉树
4.1 重建逻辑
- 先序遍历的第一个节点是根节点。
- 在中序遍历中找到该根节点，其左边是左子树，右边是右子树。
- 递归处理左子树和右子树。
示例步骤
- 先序第一个元素
6是根节点。 - 在中序中找到
6，左边是[2,3,4]，右边是[7,12,15,19]。 - 接下来在先序中取下一个元素
3，它属于左子树。 - 在中序中找到
3，左边是2，右边是4。 - 继续递归，直到整棵树构建完成。
4.2 算法实现（伪代码）
algorithm BuildTree(preorder, inorder):
// INPUT
// preorder = array of nodes in preorder traversal
// inorder = array of nodes in inorder traversal
// preorderIndex = global variable initialized to 0
// OUTPUT
// Reconstructs the binary tree from preorder and inorder traversal and returns the root node
node <- preorder[preorderIndex]
preorderIndex <- preorderIndex + 1
inorderIndex <- the index of node in inorder
inorderLeft <- inorder[0 : inorderIndex]
inorderRight <- inorder[inorderIndex + 1 : length(inorder)]
if length(inorderLeft) = 0 and length(inorderRight) = 0:
return node
node.left <- buildTree(preorder, inorderLeft)
node.right <- buildTree(preorder, inorderRight)
return node
5. 从后序与中序重建二叉树
5.1 重建逻辑
- 后序遍历的最后一个节点是根节点。
- 在中序中找到该节点，左边是左子树，右边是右子树。
- 递归处理右子树，再处理左子树（因为后序遍历顺序是左→右→根）。
示例步骤
- 后序最后一个元素
6是根节点。 - 在中序中找到
6，左边是左子树[2,3,4]，右边是右子树[7,12,15,19]。 - 后序倒数第二个元素是
19，属于右子树。 - 递归重建右子树和左子树。
5.2 算法实现（伪代码）
algorithm BuildTreePostIn(postorder, inorder):
// INPUT
// postorder = array of nodes in postorder traversal
// inorder = array of nodes in inorder traversal
// postorderIndex = global variable initialized to the index of the last node: length(postorder) - 1
// OUTPUT
// reconstructs the binary tree from postorder and inorder traversal and returns the root node
node <- postorder[postorderIndex]
postorderIndex <- postorderIndex - 1
inorderIndex <- the index of node in inorder
inorderLeft <- inorder[0 : inorderIndex]
inorderRight <- inorder[inorderIndex + 1 : length(inorder)]
if length(inorderRight) = 0 and length(inorderLeft) = 0:
return node
node.right <- buildTreePostIn(postorder, inorderRight)
node.left <- buildTreePostIn(postorder, inorderLeft)
return node
6. 从先序与后序重建二叉树
6.1 使用前提
⚠️ 只能用于满二叉树。否则无法区分左右孩子。
示例说明
我们以下图为例：
这两棵树的先序和后序是相同的，因此无法区分结构。
6.2 重建逻辑（满二叉树）
- 先序第一个元素是根节点。
- 先序下一个元素是左孩子。
- 在后序中找到该左孩子，确定其子树范围。
- 递归构建左右子树。
6.3 算法实现（伪代码）
algorithm BuildTreePrePost(preorder, postorder):
// INPUT
// preorder = array of nodes in preorder traversal
// postorder = array of nodes in postorder traversal
// preorderIndex = global variable initialized to 0
// OUTPUT
// reconstructs the full binary tree from preorder and postorder traversal and returns the root node
if preorderIndex >= length(preorder):
return null
node <- preorder[preorderIndex]
if preorderIndex >= length(preorder) or node == postorder[length(postorder) - 1]:
preorderIndex <- preorderIndex + 1
return node
leftChild <- preorder[preorderIndex + 1]
postorderLeftIndex <- indexOf(postorder, leftChild)
postorderLeft <- postorder[0 : postorderLeftIndex + 1]
postorderRight <- postorder[postorderLeftIndex + 1 : length(postorder) - 1]
node.left <- buildTreePrePost(preorder, postorderLeft)
node.right <- buildTreePrePost(preorder, postorderRight)
return node
7. 总结
本文介绍了三种通过深度优先遍历重建二叉树的方法：
| 组合方式 | 是否可唯一重建 | 条件说明 |
|---|---|---|
| 中序 + 先序 | ✅ 是 | 通用方法 |
| 中序 + 后序 | ✅ 是 | 通用方法 |
| 先序 + 后序 | ✅ 是 | 仅限于满二叉树（每个节点有0或2个子节点） |
📌 踩坑提醒：不要尝试用先序+后序去重建非满二叉树，否则会遇到歧义结构，无法唯一还原。
通过这些方法，我们可以根据已知的遍历顺序，递归重建原始二叉树结构。这在算法题、编译器设计、数据结构恢复等场景中有广泛应用。