知识总结

二叉树的定义

每个节点最多有两个子节点（左子节点和右子节点）的树。

三种遍历方式

遍历示例

A
     / \
    B   C
   / \   \
  D   E   F

• 前序：A B D E C F
• 中序：D B E A C F
• 后序：D E B F C A
• 层序：A B C D E F

由遍历序列还原二叉树（初赛重点）

• 前序 + 中序 → 可以唯一确定二叉树
• 后序 + 中序 → 可以唯一确定二叉树
• 前序 + 后序 → 不能唯一确定（除非是满二叉树）

还原方法：

1. 前序的第一个元素（或后序的最后一个元素）是根
2. 在中序中找到根，左边是左子树，右边是右子树
3. 递归处理左右子树

层序遍历

使用队列实现，逐层从左到右访问所有节点。