知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 07 - 构造树专题总结 ## 通用模板 所有构造树题目都是同一个套路: ```java TreeNode build(数据源, int lo, int hi) { if (lo > hi) return null; // 1. 递归终止 确定根节点的值; // 2. 找根 TreeNode root = new TreeNode(val); 确定左右子树的范围; // 3. 划分 root.left = build(数据源, 左边范围); // 4. 递归左 root.right = build(数据源, 右边范围); // 5. 递归右 return root; } ``` ## 各题的"找根"和"划分"方式 | 题目 | 如何找根 | 如何划分左右 | |------|---------|------------| | 105 前序+中序 | 前序的当前元素(preIdx++) | 中序中根的位置,左边=左子树,右边=右子树 | | 106 中序+后序 | 后序的当前元素(postIdx--) | 同上,但先右后左 | | 654 最大二叉树 | 区间内最大值 | 最大值左边=左子树,右边=右子树 | | 108 有序数组→BST | 区间中间元素 | 中间左边=左子树,右边=右子树 | | 109 有序链表→BST | 快慢指针找中点 / 中序模拟 | 同 108 | | 1008 前序→BST | 前序的当前元素 | BST 性质:< 根的在左,> 根的在右 | ## 关键区别:普通二叉树 vs BST ``` 普通二叉树: 没有大小关系 → 需要两个遍历序列配合才能唯一确定一棵树 前序+中序 ✓(105) 中序+后序 ✓(106) 前序+后序 ✗(不能唯一确定,因为无法区分左右子树) BST: 有"左 < 根 < 右"的性质 → 一个遍历序列就够了 前序 ✓(1008) 后序 ✓(类似 1008 反过来) 中序 ✗(中序就是排序数组,无法确定根) ``` ## 递归顺序的重要性 ``` 105 题(前序+中序): 前序 = 根→左→右 递归顺序:先左后右 ✓(和前序一致) 106 题(中序+后序): 后序反过来 = 根→右→左 递归顺序:先右后左 ✓(和后序反序一致) 如果搞反了,preIdx/postIdx 的推进顺序就会错乱,构造出错误的树。 ``` ## 面试技巧 1. **先画图**:拿到题目先用示例画出树的结构,理解输入和输出的关系 2. **找规律**:确定"根在哪"和"左右怎么分" 3. **套模板**:所有构造树题目都是同一个递归框架 4. **注意边界**:`lo > hi` 返回 null,索引不要越界 ## 延伸题目 | 题目 | LeetCode | 思路 | |------|----------|------| | 根据前序和后序遍历构造二叉树 | 889 | 前序第二个是左子树根,在后序中找到它确定左子树范围 | | 序列化和反序列化二叉树 | 297 | 前序遍历序列化,递归反序列化(本质也是构造树) | | 从前序遍历还原二叉树 | 1028 | 用破折号数量确定深度,栈辅助构造 | --- 上一篇:[06 - 前序遍历构造 BST](./06-bst-from-preorder.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入