知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 02 - 从中序与后序遍历序列构造二叉树 ## 题目(LeetCode 106) 给定两个整数数组 `inorder` 和 `postorder`,其中 `inorder` 是二叉树的中序遍历,`postorder` 是同一棵树的后序遍历,请构造二叉树并返回其根节点。 ``` 输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3] 输出:[3,9,20,null,null,15,7] ``` ## 核心思路 和 105 题几乎一样,区别在于: - 105 题:前序的**第一个**是根 → `preIdx` 从左往右 - 106 题:后序的**最后一个**是根 → `postIdx` 从右往左 而且后序是"左→右→根",反过来就是"根→右→左",所以要**先构造右子树,再构造左子树**。 ``` postorder: [9, 15, 7, 20, | 3] ↑ 根(最后一个) 反向遍历 postorder:3, 20, 7, 15, 9 根→右子树→左子树 ``` ## 代码 ```java class Solution { private Map<Integer, Integer> inorderMap = new HashMap<>(); private int postIdx; public TreeNode buildTree(int[] inorder, int[] postorder) { postIdx = postorder.length - 1; // 从后往前 for (int i = 0; i < inorder.length; i++) { inorderMap.put(inorder[i], i); } return build(postorder, 0, inorder.length - 1); } private TreeNode build(int[] postorder, int inLo, int inHi) { if (inLo > inHi) return null; int rootVal = postorder[postIdx--]; // 从后往前取根 TreeNode root = new TreeNode(rootVal); int mid = inorderMap.get(rootVal); // 注意:先右后左!(后序反过来是 根→右→左) root.right = build(postorder, mid + 1, inHi); root.left = build(postorder, inLo, mid - 1); return root; } } ``` ## 和 105 题的对比 | | 105(前序+中序) | 106(中序+后序) | |--|--------|--------| | 根节点来源 | 前序第一个 | 后序最后一个 | | 索引方向 | preIdx 从左往右 ++ | postIdx 从右往左 -- | | 递归顺序 | 先左后右 | 先右后左 | | 其他逻辑 | 完全一样 | 完全一样 | 记住这个对比,两道题本质是镜像关系。 ## 复杂度 - 时间 O(n),空间 O(n) --- 上一篇:[01 - 从前序与中序遍历序列构造二叉树](./01-build-from-preorder-inorder.md) | 下一篇:[03 - 最大二叉树](./03-maximum-binary-tree.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入