二叉树 #
1、解题思路 #
遍历:通过遍历一遍树可以完成任务,则用
traverse
函数配合外部变量
实现。 =》回溯递归分解:通过子问题/子树的答案得到问题的解,则用
traverse
函数递归,利用返回值。=》 动态规划 =》后序
2、关注点 #
单独抽出一个节点,它需要做什么?在前/中/后序什么时候做?
3、融会贯通 #
3.1、遍历函数 traverse() 的理解 #
迭代/递归遍历数组、链表、树没什么区别!
数组 #
/* 迭代遍历数组 */
void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
}
}
/* 递归遍历数组 */
void traverse(int[] arr, int i) {
if (i == arr.length) {
return;
}
// 前序位置
traverse(arr, i + 1);
// 后序位置
}
链表 #
/* 迭代遍历单链表 */
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
}
}
/* 递归遍历单链表 */
void traverse(ListNode head) {
if (head == null) {
return;
}
// 前序位置
traverse(head.next);
// 后序位置
}
3.2、快速排序 -> 前序遍历 #
构造分界点 -> 递归左右
3.3、归并排序 -> 后序遍历 #
先排左右 -> 合并
4、题目 #
一棵二叉树共有几个节点?
- 普通二叉树
- 后序遍历 - O(N)
- 满二叉树
- 计算树的高度 -> 2^h - 1 ( O(logN)
- 完全二叉树
- 记录左、右子树的高度:同,则满;否则普通树
- O(logNlogN):一棵完全二叉树的两棵子树,至少有一棵是满二叉树。因此两个递归只有一个会真的递归下去,满的一定会触发hl == hr,只消耗 O(logN) 的复杂度而不会继续递归。综上,算法的递归深度就是树的高度 O(logN),每次递归所花费的时间就是 while 循环,需要 O(logN),所以总体的时间复杂度是 O(logNlogN)。
- 普通二叉树
翻转二叉树
- 前序序或后序遍历
将二叉树展开为链表
- 后序遍历
- 将原先的右子树接到当前右子树的末端
填充二叉树每个节点的下一个右侧节点指针
- 定义:填充以root为根的树的…?不符合,不能跨子树 -> 传入左右节点,分别递归
- 该做:将传入的两个节点连接
- 前序
构造最大二叉树
- 定义:将给定的子数组构造最大二叉树
- 该做:找到最大值,作为root, 并赋值左右节点
- 前序
- 涉及数组:辅助函数,控制索引
前序和中序遍历结果构造二叉树
- 定义:给定的子数组构造二叉树
- 该做:找到root节点,确定左右子树的子数组,赋值左右节点。
- 前序
- 涉及数组:辅助函数,控制索引,画图
寻找重复子树
- 定义:给定的子树判断重复子树
- 该做:
- 以我为root的子树长啥样
- 其他子树长啥样
- 描述与对比:二叉树序列化
- 后序!
二叉树序列化与反序列化
- 序列化:前序遍历(或后序遍历)
- 反序列化:因为包含了空指针的信息,前序遍历,先左后右即可。(或先右后左)
- 层次遍历框架:从队列中取根节点,然后把子节点存进队列
剑8:二叉树的下一个节点(给定带父指针二叉树和一个节点,找中序遍历序列的下一个节点)
- 节点有右子树,最左子节点就是
- 没有右子树
- 左叶子节点,那父节点就是下一个
- 右叶子节点,找到一个是它父节点的左孩子的节点
剑26:给两棵二叉树,判断是不是子结构
- 定义:给定的子树有没有包含
- 该做:判断结构是否相同
- 定义:判断给定的子树是否相同
- 该做:值相等?
- 前序
- 前序
剑28:判断一颗二叉树是不是对称的
- 分析:前序遍历和对称前序遍历序列是否一样。1树变2树
- 定义:给定的两棵树是不是一样的
- 该做:值相等
- 前序
剑32:从上到下打印二叉树
- 队列/栈
- 设置对应的变量
剑34:给一棵二叉树和一个整数,打印和为整数的所有路径
- 定义:给定的子树是否有和为某个整数的路径
- 该做:加上自己的值。为了打印,遍历时节点入栈,返回父节点之前,在路径上删除当前节点
- 前序
剑55:求二叉树的深度:知道左和右子树的深度,取最大者就可以
二叉搜索树中第k小/大的元素
- 中序遍历即为升序排列的结果
把二叉搜索树转换为累加树
- 利用特性
判断BST的合法性
- 如果当前节点会对下面的子节点有整体影响,使用辅助函数,增加函数参数列表,在参数中携带额外信息,将这种约束传递给子树的所有节点
在BST中搜索一个数
- 针对BST的遍历框架
在BST中插入一个数
- 找到空位置,插入新节点
在BST中删除一个数
- 先找,找到后删除
- 叶子节点 - return null
- 一个子节点 - 返回该子节点
- 两个子节点 - 左子树最大 或 右子树最小
给一个正整数n, 计算共有多少种不同结构的BST结构
- 分析:先确定根节点:n种情况,确认后,左子树组合数 * 右子树组合数
- 定义:计算闭区间 [lo, hi] 组成的BST个数
- 后序
- 消除重叠子问题:备忘录
给一个正整数n, 构建所有的BST
- 分析:先穷举根节点的所有可能 - 递归构造子BST - 穷举左右子树的组合
- 定义:构造闭区间 [lo, hi] 组成的BST,返回根节点
- 后序
- 消除重叠子问题:备忘录
给一棵二叉树,找到节点之和最大的那颗BST
- 分析:左右子树是不是BST?加上自己是不是BST? 记录节点之和
- 定义:给定子树,返回int[] {是不是BST,最小值,最大值,和}
- 该做:得到左子树、右子树的结果,判断并计算
- 后序遍历
- 如果当前节点要做的事情需要通过左右子树的计算结果推导出来,就要用到后序遍历。
剑33:给一个整数数组,判断是不是某二叉搜索树的后序遍历结果
- 定义:给定子数组,是不是
- 该做:确定左子树、右子树的子数组