12.3 构建二叉树问题¶
Question
给定一棵二叉树的前序遍历 preorder 和中序遍历 inorder ,请从中构建二叉树,返回二叉树的根节点。假设二叉树中没有值重复的节点(如图 12-5 所示)。
图 12-5 构建二叉树的示例数据
图解 12-5:由前序与中序序列重建五节点二叉树
由前序 [3,9,2,1,7] 与中序 [9,3,1,2,7],唯一重建以 3 为根的五节点二叉树。
已知一棵二叉树的前序遍历序列 preorder = [3, 9, 2, 1, 7] 和中序遍历序列 inorder = [9, 3, 1, 2, 7],且树中所有节点的值互不重复。
前序遍历遵循“根 → 左子树 → 右子树”的访问顺序,中序遍历遵循“左子树 → 根 → 右子树”的访问顺序。利用两条序列的互补位置关系,可以从中唯一还原整棵二叉树。
画面左侧展示待重建的目标二叉树:根节点为 3,其左子节点为 9、右子节点为 2;节点 2 的左子节点为 1、右子节点为 7;节点 9、1、7 均为叶节点。
画面右侧上下排列这两条遍历序列,并通过向左的箭头“重建二叉树”指向左侧树结构。结合遍历规则可印证:前序首元素 3 确定整棵树的根;在中序中,3 左侧仅有 9,说明左子树只含节点 9;3 右侧为 [1, 2, 7],对应前序后三项 [2, 1, 7],说明右子树以 2 为根、以 1 和 7 为左右子节点。
注意这是一棵普通二叉树而非二叉搜索树,节点位置由遍历次序决定,并不要求左子节点的值小于父节点(例如左子节点 9 大于根节点 3)。
前序负责定位子树根,中序负责划分子树成员范围;在节点值互不重复的前提下,二者共同唯一确定这棵树。
1. 判断是否为分治问题¶
原问题定义为从 preorder 和 inorder 构建二叉树,是一个典型的分治问题。
- 问题可以分解:从分治的角度切入,我们可以将原问题划分为两个子问题:构建左子树、构建右子树,加上一步操作:初始化根节点。而对于每棵子树(子问题),我们仍然可以复用以上划分方法,将其划分为更小的子树(子问题),直至达到最小子问题(空子树)时终止。
- 子问题是独立的:左子树和右子树是相互独立的,它们之间没有交集。在构建左子树时,我们只需关注中序遍历和前序遍历中与左子树对应的部分。右子树同理。
- 子问题的解可以合并:一旦得到了左子树和右子树(子问题的解),我们就可以将它们链接到根节点上,得到原问题的解。
2. 如何划分子树¶
根据以上分析,这道题可以使用分治来求解,但如何通过前序遍历 preorder 和中序遍历 inorder 来划分左子树和右子树呢?
根据定义,preorder 和 inorder 都可以划分为三个部分。
- 前序遍历:
[ 根节点 | 左子树 | 右子树 ],例如图 12-5 的树对应[ 3 | 9 | 2 1 7 ]。 - 中序遍历:
[ 左子树 | 根节点 | 右子树 ],例如图 12-5 的树对应[ 9 | 3 | 1 2 7 ]。
以上图数据为例,我们可以通过图 12-6 所示的步骤得到划分结果。
- 前序遍历的首元素 3 是根节点的值。
- 查找根节点 3 在
inorder中的索引,利用该索引可将inorder划分为[ 9 | 3 | 1 2 7 ]。 - 根据
inorder的划分结果,易得左子树和右子树的节点数量分别为 1 和 3 ,从而可将preorder划分为[ 3 | 9 | 2 1 7 ]。
图 12-6 在前序遍历和中序遍历中划分子树
图解 12-6:用中序位置切分左右子树,再切分前序
前序首项 3 定根,中序分出左子树 [9] 与右子树 [1,2,7],再按节点数切分前序。
输入为前序遍历 preorder = [3, 9, 2, 1, 7] 与中序遍历 inorder = [9, 3, 1, 2, 7],所有节点值互不重复。
前序先访问根,因此前序首元素 3 就是根。
在中序中找到 3;它左边只有 [9],右边是 [1,2,7],所以左右子树分别有 1 个和 3 个节点。
据此切分前序:根 3 之后的一个元素 [9] 属于左子树,其余 [2,1,7] 属于右子树。右子树的两种遍历包含相同节点,访问顺序不同。
画面左侧还画出供对照的完整五节点树。下方第一张表列出本次切分的子问题序列,第二张表列出图中树的全部连接。
| 部分 | 节点数 | 前序 | 中序 |
|---|---|---|---|
| 根 | 1 | [3] | [3] |
| 左子树 | 1 | [9] | [9] |
| 右子树 | 3 | [2,1,7] | [1,2,7] |
| 节点 | 左子节点 | 右子节点 |
|---|---|---|
| 3 | 9 | 2 |
| 9 | 无 | 无 |
| 2 | 1 | 7 |
| 1 | 无 | 无 |
| 7 | 无 | 无 |
原问题由此分为左右两个独立的递归子问题。
3. 基于变量描述子树区间¶
根据以上划分方法,我们已经得到根节点、左子树、右子树在 preorder 和 inorder 中的索引区间。而为了描述这些索引区间,我们需要借助几个指针变量。
- 将当前树的根节点在
preorder中的索引记为 \(i\) 。 - 将当前树的根节点在
inorder中的索引记为 \(m\) 。 - 将当前树在
inorder中的索引区间记为 \([l, r]\) 。
如表 12-1 所示,通过以上变量即可表示根节点在 preorder 中的索引,以及子树在 inorder 中的索引区间。
表 12-1 根节点和子树在前序遍历和中序遍历中的索引
根节点在 preorder 中的索引 |
子树在 inorder 中的索引区间 |
|
|---|---|---|
| 当前树 | \(i\) | \([l, r]\) |
| 左子树 | \(i + 1\) | \([l, m-1]\) |
| 右子树 | \(i + 1 + (m - l)\) | \([m+1, r]\) |
请注意,右子树根节点索引中的 \((m-l)\) 的含义是“左子树的节点数量”,建议结合图 12-7 理解。
图 12-7 根节点和左右子树的索引区间表示
图解 12-7:用 i、l、m、r 表示构树递归的索引区间
左子树根的前序索引为 i+1,右子树根的前序索引为 i+1+(m−l),其中 m−l 为左子树节点数。
输入为前序遍历 preorder = [3, 9, 2, 1, 7] 与中序遍历 inorder = [9, 3, 1, 2, 7],节点值互不重复。
数组索引从 0 开始:i 表示当前子树根节点在 preorder 中的索引;[l, r] 表示当前子树在 inorder 中的闭区间;m 表示当前子树根节点在 inorder 中的索引。注意 m 是通过根的值在 inorder(或哈希表)中查表得到的索引,并非区间 [l, r] 的几何中点。
画面标出顶层调用的符号指针。按数组从 0 起编号可读得:根 3 的前序索引 i = 0,中序闭区间 [l, r] = [0, 4],根在中序中的索引 m = 1。因而左子树节点数 m − l = 1;这些数字索引是按图中位置换算的,图上主要标示符号。
左子树根紧跟当前根,前序索引为 i + 1。右子树根需跳过当前根及全部 m − l 个左子树节点,前序索引为 i + 1 + (m − l)。
左侧对应的树以 3 为根,左子为 9、右子为 2,2 的左、右子节点为 1、7;9、1、7 是叶节点。递归实现中遇到 l > r 的空中序区间时,调用直接返回空子树。下表公式中的 i、l、m、r 都指当前父调用;末列给出相应子问题的具体前序根索引和中序区间。
| 子问题 | 前序根索引 | 中序闭区间 | 本例 |
|---|---|---|---|
| 当前树 | i | [l,r] | 前序根索引 0,中序区间 [0,4],根值 3;根的中序索引 m=1 |
| 左子树 | i+1 | [l,m−1] | 前序根索引 1,中序区间 [0,0],根值 9 |
| 右子树 | i+1+(m−l) | [m+1,r] | 前序根索引 2,中序区间 [2,4],根值 2 |
借助指针变量 i、l、m、r 的代数关系,每次递归调用仅需传递整数索引即可精确界定左右子树,无需切片复制子数组。
4. 代码实现¶
为了提升查询 \(m\) 的效率,我们借助一个哈希表 hmap 来存储数组 inorder 中元素到索引的映射:
def dfs(
preorder: list[int],
inorder_map: dict[int, int],
i: int,
l: int,
r: int,
) -> TreeNode | None:
"""构建二叉树:分治"""
# 子树区间为空时终止
if r - l < 0:
return None
# 初始化根节点
root = TreeNode(preorder[i])
# 查询 m ,从而划分左右子树
m = inorder_map[preorder[i]]
# 子问题:构建左子树
root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
# 子问题:构建右子树
root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)
# 返回根节点
return root
def build_tree(preorder: list[int], inorder: list[int]) -> TreeNode | None:
"""构建二叉树"""
# 初始化哈希表,存储 inorder 元素到索引的映射
inorder_map = {val: i for i, val in enumerate(inorder)}
root = dfs(preorder, inorder_map, 0, 0, len(inorder) - 1)
return root
/* 构建二叉树:分治 */
TreeNode *dfs(vector<int> &preorder, unordered_map<int, int> &inorderMap, int i, int l, int r) {
// 子树区间为空时终止
if (r - l < 0)
return NULL;
// 初始化根节点
TreeNode *root = new TreeNode(preorder[i]);
// 查询 m ,从而划分左右子树
int m = inorderMap[preorder[i]];
// 子问题:构建左子树
root->left = dfs(preorder, inorderMap, i + 1, l, m - 1);
// 子问题:构建右子树
root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
// 返回根节点
return root;
}
/* 构建二叉树 */
TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
// 初始化哈希表,存储 inorder 元素到索引的映射
unordered_map<int, int> inorderMap;
for (int i = 0; i < inorder.size(); i++) {
inorderMap[inorder[i]] = i;
}
TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorder.size() - 1);
return root;
}
/* 构建二叉树:分治 */
TreeNode dfs(int[] preorder, Map<Integer, Integer> inorderMap, int i, int l, int r) {
// 子树区间为空时终止
if (r - l < 0)
return null;
// 初始化根节点
TreeNode root = new TreeNode(preorder[i]);
// 查询 m ,从而划分左右子树
int m = inorderMap.get(preorder[i]);
// 子问题:构建左子树
root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
// 子问题:构建右子树
root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
// 返回根节点
return root;
}
/* 构建二叉树 */
TreeNode buildTree(int[] preorder, int[] inorder) {
// 初始化哈希表,存储 inorder 元素到索引的映射
Map<Integer, Integer> inorderMap = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
TreeNode root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
return root;
}
/* 构建二叉树:分治 */
TreeNode? DFS(int[] preorder, Dictionary<int, int> inorderMap, int i, int l, int r) {
// 子树区间为空时终止
if (r - l < 0)
return null;
// 初始化根节点
TreeNode root = new(preorder[i]);
// 查询 m ,从而划分左右子树
int m = inorderMap[preorder[i]];
// 子问题:构建左子树
root.left = DFS(preorder, inorderMap, i + 1, l, m - 1);
// 子问题:构建右子树
root.right = DFS(preorder, inorderMap, i + 1 + m - l, m + 1, r);
// 返回根节点
return root;
}
/* 构建二叉树 */
TreeNode? BuildTree(int[] preorder, int[] inorder) {
// 初始化哈希表,存储 inorder 元素到索引的映射
Dictionary<int, int> inorderMap = [];
for (int i = 0; i < inorder.Length; i++) {
inorderMap.TryAdd(inorder[i], i);
}
TreeNode? root = DFS(preorder, inorderMap, 0, 0, inorder.Length - 1);
return root;
}
/* 构建二叉树:分治 */
func dfsBuildTree(preorder []int, inorderMap map[int]int, i, l, r int) *TreeNode {
// 子树区间为空时终止
if r-l < 0 {
return nil
}
// 初始化根节点
root := NewTreeNode(preorder[i])
// 查询 m ,从而划分左右子树
m := inorderMap[preorder[i]]
// 子问题:构建左子树
root.Left = dfsBuildTree(preorder, inorderMap, i+1, l, m-1)
// 子问题:构建右子树
root.Right = dfsBuildTree(preorder, inorderMap, i+1+m-l, m+1, r)
// 返回根节点
return root
}
/* 构建二叉树 */
func buildTree(preorder, inorder []int) *TreeNode {
// 初始化哈希表,存储 inorder 元素到索引的映射
inorderMap := make(map[int]int, len(inorder))
for i := 0; i < len(inorder); i++ {
inorderMap[inorder[i]] = i
}
root := dfsBuildTree(preorder, inorderMap, 0, 0, len(inorder)-1)
return root
}
/* 构建二叉树:分治 */
func dfs(preorder: [Int], inorderMap: [Int: Int], i: Int, l: Int, r: Int) -> TreeNode? {
// 子树区间为空时终止
if r - l < 0 {
return nil
}
// 初始化根节点
let root = TreeNode(x: preorder[i])
// 查询 m ,从而划分左右子树
let m = inorderMap[preorder[i]]!
// 子问题:构建左子树
root.left = dfs(preorder: preorder, inorderMap: inorderMap, i: i + 1, l: l, r: m - 1)
// 子问题:构建右子树
root.right = dfs(preorder: preorder, inorderMap: inorderMap, i: i + 1 + m - l, l: m + 1, r: r)
// 返回根节点
return root
}
/* 构建二叉树 */
func buildTree(preorder: [Int], inorder: [Int]) -> TreeNode? {
// 初始化哈希表,存储 inorder 元素到索引的映射
let inorderMap = inorder.enumerated().reduce(into: [:]) { $0[$1.element] = $1.offset }
return dfs(preorder: preorder, inorderMap: inorderMap, i: inorder.startIndex, l: inorder.startIndex, r: inorder.endIndex - 1)
}
/* 构建二叉树:分治 */
function dfs(preorder, inorderMap, i, l, r) {
// 子树区间为空时终止
if (r - l < 0) return null;
// 初始化根节点
const root = new TreeNode(preorder[i]);
// 查询 m ,从而划分左右子树
const m = inorderMap.get(preorder[i]);
// 子问题:构建左子树
root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
// 子问题:构建右子树
root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
// 返回根节点
return root;
}
/* 构建二叉树 */
function buildTree(preorder, inorder) {
// 初始化哈希表,存储 inorder 元素到索引的映射
let inorderMap = new Map();
for (let i = 0; i < inorder.length; i++) {
inorderMap.set(inorder[i], i);
}
const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
return root;
}
/* 构建二叉树:分治 */
function dfs(
preorder: number[],
inorderMap: Map<number, number>,
i: number,
l: number,
r: number
): TreeNode | null {
// 子树区间为空时终止
if (r - l < 0) return null;
// 初始化根节点
const root: TreeNode = new TreeNode(preorder[i]);
// 查询 m ,从而划分左右子树
const m = inorderMap.get(preorder[i]);
// 子问题:构建左子树
root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
// 子问题:构建右子树
root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
// 返回根节点
return root;
}
/* 构建二叉树 */
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
// 初始化哈希表,存储 inorder 元素到索引的映射
let inorderMap = new Map<number, number>();
for (let i = 0; i < inorder.length; i++) {
inorderMap.set(inorder[i], i);
}
const root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
return root;
}
/* 构建二叉树:分治 */
TreeNode? dfs(
List<int> preorder,
Map<int, int> inorderMap,
int i,
int l,
int r,
) {
// 子树区间为空时终止
if (r - l < 0) {
return null;
}
// 初始化根节点
TreeNode? root = TreeNode(preorder[i]);
// 查询 m ,从而划分左右子树
int m = inorderMap[preorder[i]]!;
// 子问题:构建左子树
root.left = dfs(preorder, inorderMap, i + 1, l, m - 1);
// 子问题:构建右子树
root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r);
// 返回根节点
return root;
}
/* 构建二叉树 */
TreeNode? buildTree(List<int> preorder, List<int> inorder) {
// 初始化哈希表,存储 inorder 元素到索引的映射
Map<int, int> inorderMap = {};
for (int i = 0; i < inorder.length; i++) {
inorderMap[inorder[i]] = i;
}
TreeNode? root = dfs(preorder, inorderMap, 0, 0, inorder.length - 1);
return root;
}
/* 构建二叉树:分治 */
fn dfs(
preorder: &[i32],
inorder_map: &HashMap<i32, i32>,
i: i32,
l: i32,
r: i32,
) -> Option<Rc<RefCell<TreeNode>>> {
// 子树区间为空时终止
if r - l < 0 {
return None;
}
// 初始化根节点
let root = TreeNode::new(preorder[i as usize]);
// 查询 m ,从而划分左右子树
let m = inorder_map.get(&preorder[i as usize]).unwrap();
// 子问题:构建左子树
root.borrow_mut().left = dfs(preorder, inorder_map, i + 1, l, m - 1);
// 子问题:构建右子树
root.borrow_mut().right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r);
// 返回根节点
Some(root)
}
/* 构建二叉树 */
fn build_tree(preorder: &[i32], inorder: &[i32]) -> Option<Rc<RefCell<TreeNode>>> {
// 初始化哈希表,存储 inorder 元素到索引的映射
let mut inorder_map: HashMap<i32, i32> = HashMap::new();
for i in 0..inorder.len() {
inorder_map.insert(inorder[i], i as i32);
}
let root = dfs(preorder, &inorder_map, 0, 0, inorder.len() as i32 - 1);
root
}
/* 构建二叉树:分治 */
TreeNode *dfs(int *preorder, int *inorderMap, int i, int l, int r, int size) {
// 子树区间为空时终止
if (r - l < 0)
return NULL;
// 初始化根节点
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->val = preorder[i];
root->left = NULL;
root->right = NULL;
// 查询 m ,从而划分左右子树
int m = inorderMap[preorder[i]];
// 子问题:构建左子树
root->left = dfs(preorder, inorderMap, i + 1, l, m - 1, size);
// 子问题:构建右子树
root->right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r, size);
// 返回根节点
return root;
}
/* 构建二叉树 */
TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize) {
// 初始化哈希表,存储 inorder 元素到索引的映射
int *inorderMap = (int *)malloc(sizeof(int) * MAX_SIZE);
for (int i = 0; i < inorderSize; i++) {
inorderMap[inorder[i]] = i;
}
TreeNode *root = dfs(preorder, inorderMap, 0, 0, inorderSize - 1, inorderSize);
free(inorderMap);
return root;
}
/* 构建二叉树:分治 */
fun dfs(
preorder: IntArray,
inorderMap: Map<Int?, Int?>,
i: Int,
l: Int,
r: Int
): TreeNode? {
// 子树区间为空时终止
if (r - l < 0) return null
// 初始化根节点
val root = TreeNode(preorder[i])
// 查询 m ,从而划分左右子树
val m = inorderMap[preorder[i]]!!
// 子问题:构建左子树
root.left = dfs(preorder, inorderMap, i + 1, l, m - 1)
// 子问题:构建右子树
root.right = dfs(preorder, inorderMap, i + 1 + m - l, m + 1, r)
// 返回根节点
return root
}
/* 构建二叉树 */
fun buildTree(preorder: IntArray, inorder: IntArray): TreeNode? {
// 初始化哈希表,存储 inorder 元素到索引的映射
val inorderMap = HashMap<Int?, Int?>()
for (i in inorder.indices) {
inorderMap[inorder[i]] = i
}
val root = dfs(preorder, inorderMap, 0, 0, inorder.size - 1)
return root
}
### 构建二叉树:分治 ###
def dfs(preorder, inorder_map, i, l, r)
# 子树区间为空时终止
return if r - l < 0
# 初始化根节点
root = TreeNode.new(preorder[i])
# 查询 m ,从而划分左右子树
m = inorder_map[preorder[i]]
# 子问题:构建左子树
root.left = dfs(preorder, inorder_map, i + 1, l, m - 1)
# 子问题:构建右子树
root.right = dfs(preorder, inorder_map, i + 1 + m - l, m + 1, r)
# 返回根节点
root
end
### 构建二叉树 ###
def build_tree(preorder, inorder)
# 初始化哈希表,存储 inorder 元素到索引的映射
inorder_map = {}
inorder.each_with_index { |val, i| inorder_map[val] = i }
dfs(preorder, inorder_map, 0, 0, inorder.length - 1)
end
可视化运行
图 12-8 展示了构建二叉树的递归过程,各个节点是在向下“递”的过程中建立的,而各条边(引用)是在向上“归”的过程中建立的。
图 12-8 构建二叉树的递归过程
图解 12-8:递归构树:向下创建节点,返回时连接子树
向下递进时依次创建节点 3、9、2、1、7,向上回溯返回时才将子树连接到父节点,最终建成五节点树。
输入为前序遍历 preorder = [3, 9, 2, 1, 7] 与中序遍历 inorder = [9, 3, 1, 2, 7],节点值互不重复。
每个递归子问题先从前序有效段首元素初始化当前根节点(向下“递”时创建节点),再按中序位置划分并递归构建左、右子树;当子调用返回子树根节点后,父调用才将其赋给当前根的 left 或 right 引用(向上“归”时建立连边)。空区间调用直接返回 None。
九幅画面展示创建节点或接回子树的时刻;空区间返回 None 的调用未单独拆成画面。每步的“构树第 N 步”表列出此时全部已创建节点及引用。“未连接”表示相应子树尚待构建或返回连接;“无”表示该节点确实没有这个子节点。
| 索引 | 前序值 | 中序值 |
|---|---|---|
| 0 | 3 | 9 |
| 1 | 9 | 3 |
| 2 | 2 | 1 |
| 3 | 1 | 2 |
| 4 | 7 | 7 |
创建根节点 3
进入顶层调用 i = 0、中序区间 [0, 4],由前序首项创建根 3。在中序索引 1 处找到 3,左子树为 [9],右子树的中序为 [1, 2, 7]、前序为 [2, 1, 7]。当前只创建了根 3,没有父子边;接下来先递归构建左子树。
构树第 1 步:创建根节点 3 后的节点及引用 节点 左子节点 右子节点 3 未连接 未连接 创建叶节点 9
进入左子问题 i = 1、中序区间 [0, 0],创建节点 9。它的左右中序子区间均为空,对应空子树调用返回 None,所以 9 是叶节点。构建节点 9 的调用尚未把它返回给根 3,当前两个节点之间没有连边。
构树第 2 步:创建叶节点 9 后的节点及引用 节点 左子节点 右子节点 3 未连接 未连接 9 无 无 连接左子树 9
构建节点 9 的调用将它返回给根 3,父调用执行 3.left = 9,建立第一条边。根 3 的右子树尚待构建,接下来转向右子问题。
构树第 3 步:连接左子树 9 后的节点及引用 节点 左子节点 右子节点 3 9 未连接 9 无 无 创建右子树根 2
进入右子问题 i = 2、中序区间 [2, 4],从有效前序段 [2, 1, 7] 的首项创建节点 2。节点 2 在中序中的索引 m = 3,其左子问题为 [1]、右子问题为 [7]。当前 3.left = 9 保持不变;2 的两侧尚未连接,以 2 为根的调用尚未返回给 3,因此 3 与 2 之间没有连边。
构树第 4 步:创建右子树根 2 后的节点及引用 节点 左子节点 右子节点 3 9 未连接 9 无 无 2 未连接 未连接 创建叶节点 1
进入节点 2 的左子问题 i = 3、中序区间 [2, 2],创建叶节点 1。它两侧的中序子区间为空,但构建节点 1 的调用尚未把它返回给节点 2。当前已创建四个节点,只建立了 3.left = 9;1 未接到 2,2 也未接回 3。
构树第 5 步:创建叶节点 1 后的节点及引用 节点 左子节点 右子节点 3 9 未连接 9 无 无 2 未连接 未连接 1 无 无 连接节点 2 的左子树
构建节点 1 的调用返回给节点 2,父调用执行 2.left = 1。当前已建立 3.left = 9 和 2.left = 1;节点 2 的右子问题 [7] 尚待构建,2 仍未返回并连接到 3。
构树第 6 步:连接节点 2 的左子树后的节点及引用 节点 左子节点 右子节点 3 9 未连接 9 无 无 2 1 未连接 1 无 无 创建叶节点 7
进入节点 2 的右子问题 i = 4、中序区间 [4, 4],创建最后一个叶节点 7。五个节点均已创建;当前已有 3.left = 9 和 2.left = 1,而 2.right、3.right 尚未连接。构建节点 7 的调用即将把它返回给节点 2。
构树第 7 步:创建叶节点 7 后的节点及引用 节点 左子节点 右子节点 3 9 未连接 9 无 无 2 1 未连接 1 无 无 7 无 无 连接节点 2 的右子树
构建节点 7 的调用返回给节点 2,父调用执行 2.right = 7。当前三条边为 3.left = 9、2.left = 1、2.right = 7;以 2 为根的子树已完整,准备返回给根 3,3 与 2 之间尚未连边。
构树第 8 步:连接节点 2 的右子树后的节点及引用 节点 左子节点 右子节点 3 9 未连接 9 无 无 2 1 7 1 无 无 7 无 无 连接完整右子树
以 2 为根的右子树返回给顶层调用,执行 3.right = 2,建立最后一条边。当前 3 左接 9、右接 2,2 左接 1、右接 7;9、1、7 是叶节点。四条父子边全部建立,顶层函数返回根 3,构建完成。
构树第 9 步:连接完整右子树后的节点及引用 节点 左子节点 右子节点 3 9 2 9 无 无 2 1 7 1 无 无 7 无 无
建成树的前序遍历为 [3, 9, 2, 1, 7],中序遍历为 [9, 3, 1, 2, 7],与输入一致。
每个递归函数内的前序遍历 preorder 和中序遍历 inorder 的划分结果如图 12-9 所示。
图 12-9 每个递归函数中的划分结果
图解 12-9:逐个子问题查看前序与中序的划分
根 3 拆出左叶 9 与以 2 为根的右子树,节点 2 再拆出左右叶 1、7;各节点旁标出对应的遍历有效区间。
输入为前序遍历 preorder = [3, 9, 2, 1, 7] 与中序遍历 inorder = [9, 3, 1, 2, 7],节点值互不重复。
重建出的二叉树以 3 为根,左子节点为 9,右子节点为 2;节点 2 的左右子节点分别为 1 和 7;节点 9、1、7 均为叶节点。
画面在树的五个节点旁各画出一组完整长度的 preorder 和 inorder 数组,仅将属于当前递归子问题的区间着色,其余无关位置置为浅灰色。在每个子问题中,青色代表当前子树的根节点,蓝色代表其左子树区间,紫色代表其右子树区间。
浅灰格仍是原数组的一部分,只是不属于当前子问题;叶节点的有效序列只剩根,两侧子树段均为空。下表明确写出各有效序列中的根、左段与右段。表中“左右子树根”按图中的父子边归纳。
| 当前根 | 前序有效部分:根、左、右 | 中序有效部分:左、根、右 | 左右子树根 |
|---|---|---|---|
| 3 | 根 3;左 [9];右 [2, 1, 7] | 左 [9];根 3;右 [1, 2, 7] | 左9,右2 |
| 9 | 根 9;左空;右空 | 左空;根 9;右空 | 均为空 |
| 2 | 根 2;左 [1];右 [7] | 左 [1];根 2;右 [7] | 左1,右7 |
| 1 | 根 1;左空;右空 | 左空;根 1;右空 | 均为空 |
| 7 | 根 7;左空;右空 | 左空;根 7;右空 | 均为空 |
同一个节点值在不同递归子问题的数组中承担不同的颜色角色:例如元素 2 在根 3 的顶层数组中属于紫色右子树区间,而在以 2 自身为根的子问题数组中则变为青色根元素。图中树的五个圆形节点本身均为绿色。
各子问题重复同一规则:前序定根、中序划分左右范围;叶节点两侧的空区间返回空引用。
设树的节点数量为 \(n\) ,初始化每一个节点(执行一个递归函数 dfs() )使用 \(O(1)\) 时间。因此总体时间复杂度为 \(O(n)\) 。
哈希表存储 inorder 元素到索引的映射,空间复杂度为 \(O(n)\) 。在最差情况下,即二叉树退化为链表时,递归深度达到 \(n\) ,使用 \(O(n)\) 的栈帧空间。因此总体空间复杂度为 \(O(n)\) 。