知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 从前序与中序遍历序列构造二叉树 ## 题目(LeetCode 105) 给定两个整数数组 `preorder` 和 `inorder`,其中 `preorder` 是二叉树的前序遍历,`inorder` 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 ``` 输入:preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] 输出:[3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 ``` ## 核心思路 前序遍历的第一个元素一定是根节点。在中序遍历中找到根节点的位置,左边就是左子树,右边就是右子树。 ``` preorder: [3, | 9, | 20, 15, 7] ↑ ↑ ↑ 根 左子树 右子树 inorder: [9, | 3, | 15, 20, 7] ↑ ↑ ↑ 左子树 根 右子树 步骤: 1. preorder[0] = 3 → 根节点 2. 在 inorder 中找到 3 的位置(index=1) 3. inorder 中 index 左边 [9] → 左子树(长度=1) 4. inorder 中 index 右边 [15,20,7] → 右子树(长度=3) 5. 用左子树长度去 preorder 中切分:preorder[1:2] 是左子树,preorder[2:5] 是右子树 6. 递归构造 ``` ## 手动模拟 ``` preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] 第 1 层:根 = 3 inorder 中 3 在 index=1 → 左子树长度=1,右子树长度=3 左子树:preorder=[9], inorder=[9] 右子树:preorder=[20,15,7], inorder=[15,20,7] 第 2 层(左):根 = 9 inorder 中 9 在 index=0 → 左子树长度=0,右子树长度=0 → 叶子节点 第 2 层(右):根 = 20 inorder 中 20 在 index=1 → 左子树长度=1,右子树长度=1 左子树:preorder=[15], inorder=[15] 右子树:preorder=[7], inorder=[7] 第 3 层:15 和 7 都是叶子节点 结果: 3 / \ 9 20 / \ 15 7 ``` ## 代码 ```java class Solution { private Map<Integer, Integer> inorderMap = new HashMap<>(); private int preIdx = 0; public TreeNode buildTree(int[] preorder, int[] inorder) { // 用 HashMap 存中序遍历的值→索引,O(1) 查找根节点位置 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 inLo, int inHi) { if (inLo > inHi) return null; // 前序遍历的当前元素就是根 int rootVal = preorder[preIdx++]; TreeNode root = new TreeNode(rootVal); // 在中序遍历中找到根的位置 int mid = inorderMap.get(rootVal); // 先构造左子树,再构造右子树(和前序遍历顺序一致) root.left = build(preorder, inLo, mid - 1); root.right = build(preorder, mid + 1, inHi); return root; } } ``` ## 为什么用全局 preIdx 而不是传索引范围? 因为前序遍历的顺序是"根→左→右",我们递归时也是先处理左子树再处理右子树,所以 `preIdx` 自然地按前序顺序递增,不需要手动计算 preorder 的左右边界。这比传四个参数简洁得多。 ## 解法二:传四个索引范围(显式划分 preorder 边界) 不用全局变量,而是显式计算 preorder 中左右子树的索引范围。关键是通过"左子树长度"来切分 preorder。 ```java class Solution { private Map<Integer, Integer> inorderMap = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i], i); } return build(preorder, 0, preorder.length - 1, 0, inorder.length - 1); } // preLo~preHi: preorder 的范围,inLo~inHi: inorder 的范围 private TreeNode build(int[] preorder, int preLo, int preHi, int inLo, int inHi) { if (preLo > preHi || inLo > inHi) return null; int rootVal = preorder[preLo]; // 前序第一个是根 TreeNode root = new TreeNode(rootVal); int mid = inorderMap.get(rootVal); // 根在中序中的位置 int leftSize = mid - inLo; // 左子树的节点数量 // preorder 中:[preLo+1, preLo+leftSize] 是左子树,[preLo+leftSize+1, preHi] 是右子树 root.left = build(preorder, preLo + 1, preLo + leftSize, inLo, mid - 1); root.right = build(preorder, preLo + leftSize + 1, preHi, mid + 1, inHi); return root; } } ``` ``` 索引划分示意(以示例为例): preorder: [3, 9, 20, 15, 7] ↑ ↑ ↑─────↑ 根 左子树 右子树 preLo preLo+1 preLo+leftSize+1 inorder: [9, 3, 15, 20, 7] ↑ ↑ ↑─────↑ 左子树 根 右子树 inLo mid mid+1 leftSize = mid - inLo = 1 - 0 = 1 左子树 preorder 范围:[1, 1],inorder 范围:[0, 0] 右子树 preorder 范围:[2, 4],inorder 范围:[2, 4] ``` ### 和解法一的对比 | | 解法一(全局 preIdx) | 解法二(四个索引) | |--|--------|--------| | 参数个数 | 3 个(preorder, inLo, inHi) | 5 个(preorder, preLo, preHi, inLo, inHi) | | 全局变量 | 需要 preIdx | 不需要 | | 理解难度 | preIdx 自增不太直观 | 索引划分更显式清晰 | | 面试推荐 | ✓ 代码短 | ✓ 逻辑更容易讲清楚 | ## 解法三:迭代(栈) 不用递归,用栈模拟构造过程。思路比较巧妙: ``` 核心观察: 前序遍历 [3, 9, 20, 15, 7] 中,连续的元素要么是前一个的左子节点,要么是某个祖先的右子节点。 怎么判断?看中序遍历。 - 如果栈顶元素 ≠ inorder 当前元素 → 新节点是栈顶的左子节点 - 如果栈顶元素 = inorder 当前元素 → 需要回溯(弹栈),新节点是最后弹出节点的右子节点 ``` ```java class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0) return null; TreeNode root = new TreeNode(preorder[0]); Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); int inIdx = 0; for (int i = 1; i < preorder.length; i++) { TreeNode node = new TreeNode(preorder[i]); if (stack.peek().val != inorder[inIdx]) { // 栈顶 ≠ 中序当前 → 新节点是栈顶的左子节点 stack.peek().left = node; } else { // 栈顶 = 中序当前 → 回溯找到正确的父节点 TreeNode parent = null; while (!stack.isEmpty() && stack.peek().val == inorder[inIdx]) { parent = stack.pop(); inIdx++; } // 新节点是最后弹出节点的右子节点 parent.right = node; } stack.push(node); } return root; } } ``` ### 迭代过程模拟 ``` preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] i=0: root=3, stack=[3], inIdx=0 i=1: node=9 stack.peek()=3 ≠ inorder[0]=9 → 9 是 3 的左子节点 3.left = 9, stack=[3,9] i=2: node=20 stack.peek()=9 = inorder[0]=9 → 回溯 pop 9, inIdx→1, parent=9 stack.peek()=3 = inorder[1]=3 → 继续 pop 3, inIdx→2, parent=3 stack 空,停止 3.right = 20, stack=[20] i=3: node=15 stack.peek()=20 ≠ inorder[2]=15 → 15 是 20 的左子节点 20.left = 15, stack=[20,15] i=4: node=7 stack.peek()=15 = inorder[2]=15 → 回溯 pop 15, inIdx→3, parent=15 stack.peek()=20 = inorder[3]=20 → 继续 pop 20, inIdx→4, parent=20 stack 空,停止 20.right = 7, stack=[7] 结果: 3 / \ 9 20 / \ 15 7 ✓ ``` ### 迭代解法的优缺点 | 优点 | 缺点 | |------|------| | 不用递归,无栈溢出风险 | 逻辑不直观,面试不容易讲清楚 | | 不需要 HashMap | 代码较长 | | 时间 O(n),空间 O(n) | 理解成本高 | ## 三种解法总结 | | 解法一(全局 preIdx) | 解法二(四个索引) | 解法三(迭代栈) | |--|--------|--------|--------| | 代码量 | 最短 | 中等 | 最长 | | 理解难度 | 中 | 低 | 高 | | 面试推荐度 | ⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ | | 需要 HashMap | 是 | 是 | 否 | | 全局变量 | 是 | 否 | 否 | 面试建议:优先写解法一或解法二(看个人习惯),如果面试官追问"有没有迭代写法"再给解法三。 ## 复杂度 - 时间 O(n):每个节点处理一次,HashMap 查找 O(1) - 空间 O(n):HashMap + 递归栈 --- 下一篇:[02 - 从中序与后序遍历序列构造二叉树](./02-build-from-inorder-postorder.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入