朝花夕拾,看看前面学习过的二叉树相关问题
二叉树遍历
结点
1 | public class TreeNode { |
前、中、后序遍历
递归遍历,看访问顺序,递归的本质是利用栈,栈(深度优先遍历 - 递归栈)
前序 - 两种方式遍历
遍历的思路
- 定义的变量独立在方法之外
对变量进行正确的初始化
1
2
3
4
5
6
7
8
9
10
11
12
13
14public static List<Integer> preOrderReturn1(TreeNode root) {
List<Integer> list = new ArrayList<>();
process(list, root);
return list;
}
private static void process(List<Integer> list, TreeNode root) {
if (root == null) {
return;
}
list.add(root.val);
process(list, root.left);
process(list, root.right);
}
汇总的思路
- 特殊的情况正确返回(看题目要求,如果是list返回一个空的list而不是null)
将结果汇总
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16public static List<Integer> preOrderReturn2(TreeNode root) {
List<Integer> list = new ArrayList<>();
if (root == null) {
return list;
}
// 汇总
// 根的情况 + 左子树的情况 + 右子树的情况
List<Integer> leftList = preorderReturn2(root.left);
List<Integer> rightList = preorderReturn2(root.right);
list.add(root.val);
list.addAll(leftList);
list.addAll(rightList);
return list;
}
前序遍历的应用:
求二叉树中连个结点的公共祖先
站在root的角度,不用动
把二叉树看成三部分
根 + 左子树 + 右子树
如果两个结点不在root的同一颗子树中,最近公共祖先一定是root
如果两个结点中有一个是root,最近公共祖先一定是root
如果量给结点在root的同一颗子树中,吧问题留给该边的孩子解决
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33public static TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == p || root == q) {
return root;
}
boolean pInLeft = search(root.left, p);
boolean qInLeft = search(root.left, q);
if (pInLeft && qInLeft) {
return commonAncestor(root.left, p, q);
}
if (!pInLeft && !qInLeft) {
return commonAncestor(root.right, p, q);
}
return root;
}
private static boolean search(TreeNode root, TreeNode p) {
if (root == null) {
return false;
}
if (root == p) {
return true;
}
if (search(root.left, p)) {
return true;
}
return search(root.right, p);
}
- 二叉搜索树转换为双向有序链表
1. 如何从二叉搜索树中的到一个有序序列 - **中序遍历**
2. 如果我已经有一串有序序列了,就可以组成双向链表
1
2
3
4
5
6
7
8
9
TreeNode prev = null;
for (int i = 0; i < 10; i++) {
TreeNode node = new TreeNode(i);
node.prev = prev;
if (prev != null) {
prev.next = node;
}
prev = node;
}
二叉搜索树 -> 双向循环链表
- 得到有序序列 - 中序遍历
- 有序序列组成双向链表
- 层序遍历 - 队列(广度优先遍历)
- 把根结点放到队列
- 从队首去除节点
- 把该节点的左右孩纸放到队列中
递归
递归公式
根 + 左子树的递归 + 右子树的递归
终止条件
终止条件一定发生在变化的因素上,形参上
- 二叉树:空的情况 + 一个结点的树
堆
逻辑上:完全二叉树
物理上:数组
堆的基本功能:找最值
堆的两个重要操作
向下调整/堆化
前提:除了要调整的位置外,其他位置都满足堆的性质
操作
- 要调整的位置是叶子,不需要调整
- 找最大孩子的下标
- 最大孩子的位置和该位置的值比较,如果已经满足堆的性质,不需要调整
- 交换两个位置的值
- 继续调整最大孩子值(最大孩子处因为交换,可能不满足堆的性质)
建堆 - 分治
- 最后一个非叶子节点开始做向下调整
堆的应用
- 优先级队列 - PriorityQueue
- Top K
排序 | 空间复杂度 | 空间繁杂度 | 稳定性 |
---|---|---|---|
插排 | O(n^2) | O(1) | 稳定 |
选择 | O(n^2) | O(1) | 不稳定 |
冒泡 | O(n^2) | O(1) | 稳定 |
堆排 | O(n * long(n)) | O(1) | 不稳定 |
快排
确定基准值
- 边界
- 随机
- 多数取中
遍历整个待排序区间,把基准值小的放左边,大的放右边
- 两种方法:
- 左右两边向中间靠
- 从前往后遍历
- 两种方法:
优化点:和基准值相等的数处理,优化为三路排序
- 对左右两个小区间按照同样的方式去处理,直到待排序区间size <= 1
- 递归
- 非递归 - 栈
- 对左右两个小区间按照同样的方式去处理,直到待排序区间size <= 1