知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 09 - 从前序与中序遍历构造二叉树 ## 题目(LeetCode 105) 给定前序遍历和中序遍历的结果,构造出原始二叉树。 ``` 前序:[3, 9, 20, 15, 7] 中序:[9, 3, 15, 20, 7] 构造出: 3 / \ 9 20 / \ 15 7 ``` ## 大白话理解 两个关键规律: 1. 前序遍历的第一个元素一定是根节点(因为前序是"根→左→右") 2. 在中序遍历中找到根节点的位置,左边就是左子树,右边就是右子树 ``` 前序:[3, 9, 20, 15, 7] ↑ 根节点 = 3 中序:[9, 3, 15, 20, 7] ↑ ↑ ↑─────↑ 左 根 右子树 子树 左子树的节点:{9} 右子树的节点:{15, 20, 7} ``` 然后对左子树和右子树分别做同样的事情(递归): ``` 左子树: 前序:[9] → 根 = 9,没有子节点了 中序:[9] 右子树: 前序:[20, 15, 7] → 根 = 20 中序:[15, 20, 7] → 左子树 {15},右子树 {7} ``` ## 代码 ```java class Solution { private Map<Integer, Integer> inorderMap = new HashMap<>(); private int preIndex = 0; public TreeNode buildTree(int[] preorder, int[] inorder) { // 用 HashMap 存中序遍历的值→索引映射,方便快速查找根节点位置 for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i], i); } return build(preorder, 0, inorder.length - 1); } private TreeNode build(int[] preorder, int inLeft, int inRight) { if (inLeft > inRight) return null; // 前序遍历的当前元素就是根节点 int rootVal = preorder[preIndex++]; TreeNode root = new TreeNode(rootVal); // 在中序遍历中找到根节点的位置 int inRootIndex = inorderMap.get(rootVal); // 先构建左子树,再构建右子树(顺序不能反,因为 preIndex 是按前序递增的) root.left = build(preorder, inLeft, inRootIndex - 1); root.right = build(preorder, inRootIndex + 1, inRight); return root; } } ``` ### 逐行拆解 ``` preIndex:一个全局指针,指向前序数组中"下一个要用的根节点" inLeft, inRight:当前子树在中序数组中的范围 每次递归: 1. 从前序数组取出当前根节点(preIndex++) 2. 在中序数组中找到根节点位置 inRootIndex 3. inRootIndex 左边 [inLeft, inRootIndex-1] 是左子树 4. inRootIndex 右边 [inRootIndex+1, inRight] 是右子树 5. 递归构建左右子树 ``` ### 为什么先建左子树? 因为前序遍历是"根→左→右",preIndex 按顺序递增。根节点之后紧跟的是左子树的节点,所以必须先构建左子树,preIndex 才能正确推进。 ## 画图模拟 ``` 前序:[3, 9, 20, 15, 7] preIndex = 0 中序:[9, 3, 15, 20, 7] 第 1 步:preIndex=0, rootVal=3 中序中 3 的位置 = 1 左子树范围:[0, 0](只有 9) 右子树范围:[2, 4](15, 20, 7) 第 2 步:构建左子树,preIndex=1, rootVal=9 中序中 9 的位置 = 0 左子树范围:[0, -1] → null 右子树范围:[1, 0] → null → 节点 9 是叶子 第 3 步:构建右子树,preIndex=2, rootVal=20 中序中 20 的位置 = 3 左子树范围:[2, 2](只有 15) 右子树范围:[4, 4](只有 7) 第 4 步:preIndex=3, rootVal=15 → 叶子 第 5 步:preIndex=4, rootVal=7 → 叶子 最终: 3 / \ 9 20 / \ 15 7 ✓ ``` ## 类似题目 ``` 从中序与后序构造二叉树(LeetCode 106): 后序的最后一个元素是根节点 从后往前取根,先构建右子树再构建左子树(后序是"左→右→根",反过来就是"根→右→左") ``` ## 复杂度 - 时间:O(n),HashMap 查找 O(1) - 空间:O(n),HashMap + 递归栈 ## 一句话总结 前序定根,中序分左右。用一个指针在前序数组上走,用 HashMap 在中序数组中快速定位根的位置。 --- 上一篇:[08 - 二叉树的层序遍历](./08-level-order.md) | 下一篇:[10 - 二叉树的序列化与反序列化](./10-serialize.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入