二、进阶数据结构
原创
1、二叉树
1、东哥带你刷二叉树（纲领篇）
- 二叉树的最大深度（简单）
- 二叉树的直径（简单）
- 二叉树的前序遍历（简单）
1、深入理解前中后序
144 二叉树的前序遍历（简单）
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
}/* 迭代遍历数组 */
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);
// 后序位置
}List<Integer> res = new LinkedList<>();
// 返回前序遍历结果
List<Integer> preorderTraverse(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历函数
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
res.add(root.val);
traverse(root.left);
traverse(root.right);
}
2、两种解题思路
二叉树题目的递归解法可以分两类思路，第一类是遍历一遍二叉树得出答案，第二类是通过分解问题计算出答案，这两类思路分别对应着 回溯算法核心框架 和 动态规划核心框架。
<font style="color:rgb(89, 89, 89);">104 题「二叉树的最大深度」</font>
1、遍历
// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;
// 主函数
int maxDepth(TreeNode root) {
traverse(root);
return res;
}
// 二叉树遍历框架
void traverse(TreeNode root) {
if (root == null) {
// 到达叶子节点，更新最大深度
res = Math.max(res, depth);
return;
}
// 前序位置
depth++;
traverse(root.left);
traverse(root.right);
// 后序位置
depth--;
}2、分解问题
// 定义：输入根节点，返回这棵二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
// 利用定义，计算左右子树的最大深度
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 整棵树的最大深度等于左右子树的最大深度取最大值，
// 然后再加上根节点自己
int res = Math.max(leftMax, rightMax) + 1;
return res;
}
3、后序位置的特殊之处
<font style="color:rgb(89, 89, 89);"> 543 题「二叉树的直径」</font>
// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
// 对每个节点计算直径，求最大直径
traverse(root);
return maxDiameter;
}
// 遍历二叉树
void traverse(TreeNode root) {
if (root == null) {
return;
}
// 对每个节点计算直径
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
int myDiameter = leftMax + rightMax;
// 更新全局最大直径
maxDiameter = Math.max(maxDiameter, myDiameter);
traverse(root.left);
traverse(root.right);
}
//前序位置无法获取子树信息，所以只能让每个节点调用maxDepth函数去算子树的深度
// 计算二叉树的最大深度
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
return 1 + Math.max(leftMax, rightMax);
}// 记录最大直径的长度
int maxDiameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
maxDepth(root);
return maxDiameter;
}
int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftMax = maxDepth(root.left);
int rightMax = maxDepth(root.right);
// 后序位置，顺便计算最大直径
int myDiameter = leftMax + rightMax;
maxDiameter = Math.max(maxDiameter, myDiameter);
return 1 + Math.max(leftMax, rightMax);
}4、层序遍历
5、进阶题解
669 修剪二叉搜索树
124 二叉树中的最大路径和
515 每棵树行中找最大值
class Solution {
// 定义：删除 BST 中小于 low 和大于 high 的所有节点，返回结果 BST
public TreeNode trimBST(TreeNode root, int low, int high) {
if (null == root)
return null;
if (root.val < low)
//直接返回 root.right 相当于删除 root 和 左子树
return trimBST(root.right, low, high);
if (root.val > high)
//直接返回 root.left 相当于删除 root和 右子树
return trimBST(root.left, low, high);
// 闭区间 [lo, hi] 内的节点什么都不做
root.left = trimBST(root.left, low, high);
root.right = trimBST(root.right, low, high);
return root;
}
}class Solution {
int res = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
if (root == null) {
return 0;
}
// 计算单边路径和时顺便计算最大路径和
oneSideMax(root);
return res;
}
// 定义：计算从根节点 root 为起点的最大单边路径和
int oneSideMax(TreeNode root) {
if (root == null) {
return 0;
}
//处理负数的情况
int leftMaxSum = Math.max(0, oneSideMax(root.left));
int rightMaxSum = Math.max(0, oneSideMax(root.right));
// 后序遍历位置，顺便更新最大路径和
res = Math.max(res, root.val + leftMaxSum + rightMaxSum);
// 实现函数定义，左右子树的最大单边路径和加上根节点的值
// 就是从根节点 root 为起点的最大单边路径和
return Math.max(leftMaxSum, rightMaxSum) + root.val;
}
}class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new LinkedList<>();
if (null == root) {
return res;
}
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
// while 循环控制从上向下一层层遍历
while (!q.isEmpty()) {
int sz = q.size();
// 记录这一层的最大值
int levelMax = Integer.MIN_VALUE;
// for 循环控制每一层从左向右遍历 注意sz不能替换为 q.size(),因为q.size()会变化！！！
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
levelMax = Math.max(levelMax, cur.val);
if (cur.left != null)
q.offer(cur.left);
if (cur.right != null)
q.offer(cur.right);
}
res.add(levelMax);
}
return res;
}
}2、东哥带你刷二叉树（思维篇）
- 翻转二叉树（简单）
- 二叉树展开为链表（中等）
- 填充每个节点的下一个右侧节点指针（中等）
重点：
二叉树解题的思维模式分两类：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">traverse</font>函数配合外部变量来实现，这叫「遍历」的思维模式。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
无论使用哪种思维模式，你都需要思考：
如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？其他的节点不用你操心，递归函数会帮你在所有节点上执行相同的操作。
1、翻转二叉树
<font style="color:rgb(89, 89, 89);">226 题「翻转二叉树」</font>
//遍历递归模式
class Solution {
public TreeNode invertTree(TreeNode root) {
if (null == root)
return null;
invertTree(root.left);
invertTree(root.right);
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
return root;
}
}
// 遍历模式
// 主函数
TreeNode invertTree(TreeNode root) {
// 遍历二叉树，交换每个节点的子节点
traverse(root);
return root;
}
// 二叉树遍历函数
void traverse(TreeNode root) {
if (root == null) {
return;
}
/**** 前序位置 ****/
// 每一个节点需要做的事就是交换它的左右子节点
TreeNode tmp = root.left;
root.left = root.right;
root.right = tmp;
// 遍历框架，去遍历左右子树的节点
traverse(root.left);
traverse(root.right);
}
// 分解问题模式
// 定义：将以 root 为根的这棵二叉树翻转，返回翻转后的二叉树的根节点
TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
// 利用函数定义，先翻转左右子树
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
// 然后交换左右子节点
root.left = right;
root.right = left;
// 和定义逻辑自恰：以 root 为根的这棵二叉树已经被翻转，返回 root
return root;
}2、填充节点的右侧指针
<font style="color:rgb(89, 89, 89);">116 题「填充每个二叉树节点的右侧指针」</font>
class Solution {
//将二叉树想象为三叉树，二叉树 节点中间的缝隙 为三叉树的节点
public Node connect(Node root) {
if (null == root)
return null;
//遍历三叉树
traverse(root.left, root.right);
return root;
}
public void traverse(Node node1, Node node2) {
if (null == node1 || null == node2) {
return;
}
//三叉树节点内部 连接 next
node1.next = node2;
//递归遍历三叉树
//节点1
traverse(node1.left, node1.right);
//节点2
traverse(node2.left, node2.right);
//这个是虚拟节点
traverse(node1.right, node2.left);
}
}3、将二叉树展开为链表
114 将二叉树展开为链表
class Solution {
// 定义：输入节点 root，然后 root 为根的二叉树就会被拉平为一条链表
public void flatten(TreeNode root) {
if (null == root) return;
//利用函数的定义拉平左子树
flatten(root.left);
//利用函数的定义拉平右子树
flatten(root.right);
/**** 后序遍历位置 ****/
// 1、左右子树已经被拉平成一条链表
TreeNode left = root.left;
TreeNode right = root.right;
// 2、将左子树作为右子树
root.left = null;
root.right = left;
// 3、将原先的右子树接到当前右子树的末端
TreeNode p = root;
while (null != p.right) {
p = p.right;
}
p.right = right;
}
}总结：
3、东哥带你刷二叉树（构造篇）
重点：
二叉树的构造问题一般都是使用「分解问题」的思路：构造整棵树 = 根节点 + 构造左子树 + 构造右子树。
654. 最大二叉树（中等）
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return buildTree(nums, 0, nums.length - 1);
}
//在[lo,hi]坐标之间构建二叉树
public TreeNode buildTree(int[] nums, int lo, int hi) {
if (hi < lo) return null;
//找到[lo,hi]的最大值和下标
int index = -1;
int maxValue = Integer.MIN_VALUE;
for (int i = lo; i <= hi; i++) {
if (maxValue < nums[i]) {
index = i;
maxValue = nums[i];
}
}
//构建根节点
TreeNode root = new TreeNode(maxValue);
root.left = buildTree(nums, lo, index - 1);
root.right = buildTree(nums, index + 1, hi);
return root;
}
}105. 从前序与中序遍历序列构造二叉树（中等）
class Solution {
HashMap<Integer, Integer> indexMap;
public TreeNode buildTree(int[] preorder, int[] inorder) {
//将坐标缓存
indexMap = new HashMap<>(inorder.length);
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1);
}
//分解问题
public TreeNode build(int[] preorder, int prelo, int prehi, int[] inorder, int inlo, int inhi) {
if (inlo > inhi) return null;
//找到root节点
int rootValue = preorder[prelo];
//找到root节点在 中序遍历数组中的 下标
int rootIndex = indexMap.get(rootValue);
//左子树size
int leftsize = rootIndex - inlo;
TreeNode root = new TreeNode(rootValue);
root.left = build(preorder, prelo + 1, prelo + leftsize,
inorder, inlo, rootIndex - 1);
root.right = build(preorder, prelo + leftsize + 1, prehi,
inorder, rootIndex + 1, inhi);
return root;
}
}106. 从中序与后序遍历序列构造二叉树（中等）
class Solution {
HashMap<Integer, Integer> indexMap;
public TreeNode buildTree(int[] inorder, int[] postorder) {
indexMap = new HashMap<>(inorder.length);
for (int i = 0; i < inorder.length; i++) {
indexMap.put(inorder[i], i);
}
return build(inorder, 0, inorder.length - 1,
postorder, 0, postorder.length - 1);
}
public TreeNode build(int[] inorder, int inlo, int inhi,
int[] postorder, int polo, int pohi) {
if (inlo > inhi) return null;
//后续遍历的最后一个数据就是 根 节点数据
int rootValue = postorder[pohi];
int rootIndex = indexMap.get(rootValue);
int leftsize = rootIndex - inlo;
TreeNode root = new TreeNode(rootValue);
root.left = build(inorder, inlo, rootIndex - 1,
postorder, polo, polo + leftsize - 1);
root.right = build(inorder, rootIndex + 1, inhi,
postorder, polo + leftsize, pohi - 1);
return root;
}
}889. 根据前序和后序遍历构造二叉树（中等）
注意：**通过前序中序，或者后序中序遍历结果可以确定一棵原始二叉树，但是通过前序后序遍历结果无法确定原始二叉树，结果不唯一。**
class Solution {
HashMap<Integer, Integer> indexMap;
public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
indexMap = new HashMap<>(postorder.length);
for (int i = 0; i < postorder.length; i++) {
indexMap.put(postorder[i], i);
}
return build(preorder, 0, preorder.length - 1,
postorder, 0, postorder.length - 1);
}
public TreeNode build(int[] preorder, int prelo, int prehi,
int[] postorder, int polo, int pohi) {
if (prelo > prehi) {
return null;
}
if (prelo == prehi) {
return new TreeNode(preorder[prelo]);
}
//根节点
int rootValue = preorder[prelo];
//左侧根节点
//我们假设前序遍历的第二个元素是左子树的根节点，但实际上左子树有可能是空指针，
//那么这个元素就应该是右子树的根节点。由于这里无法确切进行判断，所以导致了最终答案的不唯一。
int leftRootValue = preorder[prelo + 1];
//左侧根节点后序数组索引
int leftRoorIndex = indexMap.get(leftRootValue);
//左侧数组长度
int leftsize = leftRoorIndex - polo + 1;
TreeNode root = new TreeNode(rootValue);
root.left = build(preorder, prelo + 1, prelo + 1 + leftsize - 1,
postorder, polo, leftRoorIndex);
root.right = build(preorder, prelo + leftsize + 1, prehi,
postorder, leftRoorIndex + 1, pohi - 1);
return root;
}
}4、东哥带你刷二叉树（序列化篇）
- 二叉树的序列化和反序列化（困难）
前序遍历解法
public class Codec {
String SEP = ",";
String NULL = "null";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeBuild(root, sb);
return sb.toString();
}
private void serializeBuild(TreeNode root, StringBuilder sb) {
if (null == root) {
sb.append(NULL).append(SEP);
return;
}
//前序遍历
sb.append(root.val).append(SEP);
serializeBuild(root.left, sb);
serializeBuild(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
//队列 先进先出
LinkedList<String> strings = new LinkedList<>();
for (String s : data.split(SEP)) {
strings.addLast(s);
}
return deserializeBuild(strings);
}
// 函数定义，获取队列的元素构建节点并返回
private TreeNode deserializeBuild(LinkedList<String> strings) {
if (strings.isEmpty()) return null;
/****** 前序位置 ******/
// 列表最左侧就是根节点 注意 removeFirst 方法，一定要先进先出
// 随着递归，，strings 会逐渐减少
String first = strings.removeFirst();
if (first.equals(NULL)) return null;
TreeNode rootNode = new TreeNode(Integer.valueOf(first));
rootNode.left = deserializeBuild(strings);
rootNode.right = deserializeBuild(strings);
return rootNode;
}
}后序遍历解法
注意，根据上图，从后往前在**<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">nodes</font>**列表中取元素，一定要先构造**<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">root.right</font>**子树，后构造**<font style="color:rgb(233, 105, 0);background-color:rgb(248, 248, 248);">root.left</font>**子树。
public class Codec {
String SEP = ",";
String NULL = "null";
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb = new StringBuilder();
serializeBuild(root, sb);
return sb.toString();
}
public void serializeBuild(TreeNode root, StringBuilder sb) {
if (null == root) {
sb.append(NULL).append(SEP);
return;
}
serializeBuild(root.left, sb);
serializeBuild(root.right, sb);
sb.append(root.val).append(SEP);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
LinkedList<String> strings = new LinkedList<>();
for (String s : data.split(SEP)) {
strings.addLast(s);
}
return deserializeBuild(strings);
}
public TreeNode deserializeBuild(LinkedList<String> strings) {
if (strings.isEmpty()) return null;
//注意从后面取数！！！
String last = strings.removeLast();
if (last.equals(NULL)) return null;
TreeNode node = new TreeNode(Integer.valueOf(last));
//注意先构造右边 因为后序遍历是 左右根
node.right = deserializeBuild(strings);
node.left = deserializeBuild(strings);
return node;
}
}中序遍历无法解决此问题
层序遍历解法参考东哥对应文章
void traverse(TreeNode root) {
if (root == null) return;
// 初始化队列，将 root 加入队列
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
TreeNode cur = q.poll();
/* 层级遍历代码位置 */
System.out.println(root.val);
/*****************/
if (cur.left != null) {
q.offer(cur.left);
}
if (cur.right != null) {
q.offer(cur.right);
}
}
}5、东哥带你刷二叉树（后序篇）
652.寻找重复子树（Medium）
class Solution {
//存放结果集合
List<TreeNode> resList = new LinkedList<>();
//记录所有子树的数量
HashMap<String, Integer> countMap = new HashMap<>();
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
traverse(root);
return resList;
}
String traverse(TreeNode root) {
if (null == root)
return "";
String left = traverse(root.left);
String right = traverse(root.right);
//注意此处 字符串的拼接 当left right为 “” 时，可能会有问题
String resStr = left + "," + right + "," + root.val;
Integer resCount = countMap.getOrDefault(resStr, 0);
//代表已经重复
if (1 == resCount)
resList.add(root);
//数量加1
countMap.put(resStr, resCount + 1);
return resStr;
}
}6、归并排序详解及应用
<font style="color:rgb(89, 89, 89);">递归的本质：</font>
就这么说吧，所有递归的算法，你甭管它是干什么的，本质上都是在遍历一棵（递归）树，然后在节点（前中后序位置）上执行代码，你要写递归算法，本质上就是要告诉每个节点需要做什么。
<font style="color:rgb(89, 89, 89);">912 题「排序数组」（使用归并排序）</font>
参考
https://blog.csdn.net/qq_45954420/article/details/123412430
// 定义：排序 nums[lo..hi]
void sort(int[] nums, int lo, int hi) {
if (lo == hi) {
return;
}
int mid = (lo + hi) / 2;
// 利用定义，排序 nums[lo..mid]
sort(nums, lo, mid);
// 利用定义，排序 nums[mid+1..hi]
sort(nums, mid + 1, hi);
/****** 后序位置 ******/
// 此时两部分子数组已经被排好序
// 合并两个有序数组，使 nums[lo..hi] 有序
merge(nums, lo, mid, hi);
/*********************/
}
// 将有序数组 nums[lo..mid] 和有序数组 nums[mid+1..hi]
// 合并为有序数组 nums[lo..hi]
void merge(int[] nums, int lo, int mid, int hi);看这个框架，也就明白那句经典的总结：归并排序就是先把左半边数组排好序，再把右半边数组排好序，然后把两半数组合并。
public class SortTool {
public static void main(String[] args) {
int[] arr = {5, 2, 3, 1};
//归并排序
SortTool.sortArray(arr);
SortTool.printArray(arr);
}
//打印
public static void printArray(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
// 用于辅助合并有序数组
private static int[] temp;
//数组排序
public static void sortArray(int[] nums) {
//先给辅助数组开辟内存空间
temp = new int[nums.length];
//排序
sort(nums, 0, nums.length - 1);
}
private static void sort(int[] nums, int lo, int hi) {
//单个元素不用排序
if (lo == hi)
return;
//获取中间值
int mid = lo + (hi - lo) / 2;
//排序左边
sort(nums, lo, mid);
//排序右边
sort(nums, mid + 1, hi);
//后序遍历 合并数据
merge(nums, lo, mid, hi);
}
//合并2个有序数组
private static void merge(int[] nums, int lo, int mid, int hi) {
if (lo == hi)
return;
//先将需要的数据复制到临时数组中
for (int i = lo; i <= hi; i++) {
temp[i] = nums[i];
}
//双指针
int left = lo, right = mid + 1;
for (int i = lo; i <= hi; i++) {
//注意边界问题
if (left == mid + 1) {
//左边数组遍历完毕 只移动右边
nums[i] = temp[right++];
continue;
}
if (right == hi + 1) {
//右边数组遍历完毕 只移动左边
nums[i] = temp[left++];
continue;
}
if (temp[left] < temp[right]) {
//谁小移动谁
nums[i] = temp[left++];
} else {
nums[i] = temp[right++];
}
// //注意边界问题
// if (left == mid + 1) {
//
// //左边数组遍历完毕 只移动右边
// nums[i] = temp[right++];
//
// } else if (right == hi + 1) {
//
// //右边数组遍历完毕 只移动左边
// nums[i] = temp[left++];
//
// } else if (temp[left] < temp[right]) {
// //谁小移动谁
// nums[i] = temp[left++];
// } else {
// nums[i] = temp[right++];
// }
}
}
}<font style="color:rgb(89, 89, 89);">315 题「计算右侧小于当前元素的个数」</font>
class Solution {
private class Pair {
int val, id;
Pair(int val, int id) {
// 记录数组的元素值
this.val = val;
// 记录元素在数组中的原始索引
this.id = id;
}
}
// 归并排序所用的辅助数组
private Pair[] temp;
// 记录每个元素后面比自己小的元素个数
private int[] count;
// 主函数
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
//结果数组
count = new int[n];
//辅助数组
temp = new Pair[n];
//要排序的数组
Pair[] arr = new Pair[n];
// 记录元素原始的索引位置，以便在 count 数组中更新结果
for (int i = 0; i < n; i++)
arr[i] = new Pair(nums[i], i);
// 执行归并排序arr，本题结果被记录在 count 数组中
sort(arr, 0, n - 1);
List<Integer> res = new LinkedList<>();
for (int c : count) res.add(c);
return res;
}
// 归并排序
private void sort(Pair[] arr, int lo, int hi) {
if (lo == hi) return;
int mid = lo + (hi - lo) / 2;
sort(arr, lo, mid);
sort(arr, mid + 1, hi);
merge(arr, lo, mid, hi);
}
// 合并两个有序数组
private void merge(Pair[] arr, int lo, int mid, int hi) {
for (int i = lo; i <= hi; i++) {
temp[i] = arr[i];
}
int i = lo, j = mid + 1;
for (int p = lo; p <= hi; p++) {
if (i == mid + 1) {
arr[p] = temp[j++];
} else if (j == hi + 1) {
arr[p] = temp[i++];
// 更新 count 数组
count[arr[p].id] += j - mid - 1;
} else if (temp[i].val > temp[j].val) {
arr[p] = temp[j++];
} else {
arr[p] = temp[i++];
// 更新 count 数组
count[arr[p].id] += j - mid - 1;
}
}
}
}2、<font style="color:rgb(89, 89, 89);">二叉搜索树</font>
1、东哥带你刷二叉搜索树（特性篇）
- BST第K小的元素（Medium）
- 二叉搜索树转化累加树（Medium）
- BST 转累加树（Medium）
技巧
//对于BST来说 中序遍历是升序
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.left);
// 中序遍历代码位置
print(root.val);
traverse(root.right);
}
//对于BST来说 反向中序遍历是降序
void traverse(TreeNode root) {
if (root == null) return;
traverse(root.right);
// 反向中序遍历代码位置
print(root.val);
traverse(root.left);
}230. BST第K小的元素（Medium）
class Solution {
int res = -1;
int rank = 0;
public int kthSmallest(TreeNode root, int k) {
findKthSmallest(root, k);
return res;
}
public void findKthSmallest(TreeNode root, int k) {
if (null == root)
return;
findKthSmallest(root.left, k);
//二叉搜索树 BST 中序遍历是升序
rank++;
//找到目标值
if (k == rank) {
res = root.val;
return;
}
findKthSmallest(root.right, k);
}
}538. 二叉搜索树转化累加树（Medium）
class Solution {
public TreeNode convertBST(TreeNode root) {
recursion(root);
return root;
}
private int sum = 0;
private void recursion(TreeNode root) {
if (null == root)
return;
//注意 对于BST来说 这样是降序输出!!!
recursion(root.right);
sum += root.val;
root.val = sum;
recursion(root.left);
}
}2、东哥带你刷二叉搜索树（基操篇）
98.验证二叉搜索树（Medium）
700.二叉搜索树中的搜索（Easy）
701.二叉搜索树中的插入操作（Medium）
- 删除二叉搜索树中的节点（Medium）
BST遍历框架
无需遍历所有子树！！！
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标，做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}98.验证二叉搜索树（Medium）
//错误思路：当前节点要做的事就是比较自己的值和左右子节点的值，注意这是错误思路
boolean isValidBST(TreeNode root) {
if (root == null) return true;
if (root.left != null && root.val <= root.left.val)
return false;
if (root.right != null && root.val >= root.right.val)
return false;
return isValidBST(root.left)
&& isValidBST(root.right);
}
public boolean isValidBST(TreeNode root) {
return _isValidBST(root, null, null);
}
//判断当前节点是否小于 左子树的最大值 或则 大于 右子树的最小值，要比较左右子树的最值，可以将左右边界传递进去并不断缩小边界
public boolean _isValidBST(TreeNode root, TreeNode minNode, TreeNode maxNode) {
//为null代表递归到叶子节点
if (null == root)
return true;
//前序遍历 判断当前值与最值的大小
if (minNode != null && root.val <= minNode.val) return false;
if (maxNode != null && root.val >= maxNode.val) return false;
return _isValidBST(root.left, minNode, root) && _isValidBST(root.right, root, maxNode);
}700.二叉搜索树中的搜索（Easy）
class Solution {
//二分查找
public TreeNode searchBST(TreeNode root, int target) {
if (root == null) {
return null;
}
// 去左子树搜索
if (root.val > target) {
return searchBST(root.left, target);
}
// 去右子树搜索
if (root.val < target) {
return searchBST(root.right, target);
}
//root.val = target的情况，相当于后续遍历
return root;
}
}701.二叉搜索树中的插入操作（Medium）
class Solution {
//找到合适的位置构建叶子节点
public TreeNode insertIntoBST(TreeNode root, int val) {
//找到位置构建节点
if (null == root) return new TreeNode(val);
if (root.val > val)
//去左子树插入
root.left = insertIntoBST(root.left, val);
else if (root.val < val)
//去右子树插入
root.right = insertIntoBST(root.right, val);
return root;
}
}450. 删除二叉搜索树中的节点（Medium）
class Solution {
//找到新的节点并返回
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
//root 不为空
if (key == root.val) {//找到值
//如何删除
//情况1、叶子节点都是null
//if (root.left == null && root.right == null) return null;
//情况2、只有1个非空子节点，此时就让这个非空子节点顶替自己，下面的逻辑涵盖上面的逻辑
if (root.left == null) return root.right;
if (root.right == null) return root.left;
//情况3、左右子树都不为空，从右子树中找出最小值
//找到替代节点
TreeNode minNode = getMinNode(root.right);
//更新值
root.val = minNode.val;
//转而去删除 minNode val，注意此处！！！有种滚动删除的感觉
root.right = deleteNode(root.right, minNode.val);
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
//找到比root大的最小root
private TreeNode getMinNode(TreeNode root) {
//循环查出 最小节点
while (root.left != null)
root = root.left;
return root;
}
}3、东哥带你刷二叉搜索树（构造篇）
96.不同的二叉搜索树（Easy）
class Solution {
//1 <= n <= 19
public int numTrees(int n) {
cache = new int[n + 1][n + 1];
return count(1, n);
}
//添加备忘录缓存中间结果
int[][] cache;
//计算出区间[lo,hi]所有的bst
int count(int lo, int hi) {
if (lo > hi) return 1;
if (cache[lo][hi] != 0) return cache[lo][hi];
int sum = 0;
//依次将[lo,hi]之间的树作为根节点计算 不同个bst
for (int i = lo; i <= hi; i++) {
//获取左边bst个数
int left = count(lo, i - 1);
//获取右边bst个数
int right = count(i + 1, hi);
//将不同根节点的数据累加，left * right为当前根节点 bst 个数
sum += left * right;
}
//缓存根节点数据
cache[lo][hi] = sum;
return sum;
}
}95.不同的二叉搜索树II（Medium）
class Solution {
public List<TreeNode> generateTrees(int n) {
return build(1, n);
}
//构建[lo,hi]区间的bst
List<TreeNode> build(int lo, int hi) {
List<TreeNode> res = new LinkedList<>();
if (lo > hi) {
res.add(null);
return res;
}
//遍历根节点
for (int i = lo; i <= hi; i++) {
//获取左子树可能的 根节点
List<TreeNode> left = build(lo, i - 1);
//获取右子树可能的 根节点
List<TreeNode> right = build(i + 1, hi);
//不同可能组合
for (TreeNode leftNode : left) {
for (TreeNode rightNode : right) {
TreeNode rootNode = new TreeNode(i);
rootNode.left = leftNode;
rootNode.right = rightNode;
res.add(rootNode);
}
}
}
return res;
}
}4、东哥带你刷二叉搜索树（后序篇）
<font style="color:rgb(89, 89, 89);">1373.二叉搜索子树的最大键值和（</font><font style="color:rgb(255, 0, 0);">Hard</font><font style="color:rgb(89, 89, 89);">）</font>
class Solution {
int maxSum = 0;
public int maxSumBST(TreeNode root) {
recursion(root);
return maxSum;
}
private int[] recursion(TreeNode root) {
//注意此处返回 数组的处理 是否是bst、当前二叉树最大值、当前二叉树最小值、当前二叉树和
if (null == root) return new int[]{1, Integer.MIN_VALUE, Integer.MAX_VALUE, 0};
int[] left = recursion(root.left);
int[] right = recursion(root.right);
//是否是bst、当前二叉树最大值、当前二叉树最小值、当前二叉树和
int[] res = new int[4];
//判断是否是合法的BST：左子树是 右子树是 并且root值大于左子树最大值 小于右子树最小值
if (1 == left[0] && 1 == right[0] && left[1] < root.val && root.val < right[2]) {
res[0] = 1;
res[1] = Math.max(root.val, right[1]);
res[2] = Math.min(root.val, left[2]);
res[3] = left[3] + root.val + right[3];
maxSum = Math.max(maxSum, res[3]);
} else {
res[0] = 0;
}
return res;
}
}5、快速排序详解及应用
快速排序算法（912. 排序数组（Medium））
class Solution {
public int[] sortArray(int[] nums) {
// 为了避免出现耗时的极端情况，先随机打乱
shuffle(nums);
quickSort(nums, 0, nums.length - 1);
return nums;
}
// 洗牌算法，将输入的数组随机打乱
private void shuffle(int[] nums) {
Random rand = new Random();
int n = nums.length;
for (int i = 0; i < n; i++) {
// 生成 [i, n - 1] 的随机数
int r = i + rand.nextInt(n - i);
swap(nums, i, r);
}
}
public void quickSort(int[] nums, int lo, int hi) {
if (lo >= hi) {
return;
}
//找到分界位置
int p = partiton(nums, lo, hi);
quickSort(nums, lo, p - 1);
quickSort(nums, p + 1, hi);
}
//返回已经排好序的下标
private int partiton(int[] nums, int lo, int hi) {
int value = nums[lo];
int i = lo + 1, j = hi;
while (i <= j) {
//从左侧找到第一个比目标值大的
while (nums[i] <= value && i < hi) {
i++;
}
//从右侧找到第一个比目标值小的
while (nums[j] > value && j > lo) {
j--;
}
//代码到此处代表已经找到两个需要交换数据的位置，但是需要判断是否合法
if (i >= j) {
break;
}
//找到相应的位置后交换两者的数据
swap(nums, i, j);
}
// 此时i j重合，找到分界下标，将value放到对应的位置上，也就是j上面的元素已经排好顺序！！！
swap(nums, lo, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}快速选择算法（215. 数组中的第 K 个最大元素（Medium））
class Solution {
public int findKthLargest(int[] nums, int k) {
// 首先随机打乱数组
shuffle(nums);
int lo = 0, hi = nums.length - 1;
// 转化成「排名第 k 的元素」
k = nums.length - k;
while (lo <= hi) {
//找到分界下标
int p = partiton(nums, lo, hi);
if (p < k) {
//从p的右侧找
lo = p + 1;
} else if (p > k) {
//从p的左侧找
hi = p - 1;
} else {
return nums[p];
}
}
return -1;
}
// 洗牌算法，将输入的数组随机打乱
private void shuffle(int[] nums) {
Random rand = new Random();
int n = nums.length;
for (int i = 0; i < n; i++) {
// 生成 [i, n - 1] 的随机数
int r = i + rand.nextInt(n - i);
swap(nums, i, r);
}
}
//返回已经排好序的下标
private int partiton(int[] nums, int lo, int hi) {
int value = nums[lo];
int i = lo + 1, j = hi;
while (i <= j) {
//左侧找到第一个比value大的
while (i < hi && nums[i] <= value) {
i++;
}
//右侧找到第一个比value小的
while (j > lo && nums[j] > value) {
j--;
}
//找到了 判断是否合法
if (i >= j) break;
//合法 交换位置
swap(nums, i, j);
}
//将目标值放到找到的位置上
swap(nums, lo, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}3、图论
1、图论基础
1、图
2、图的遍历
3、<font style="color:rgb(89, 89, 89);">797 题「所有可能路径」</font>
class Solution {
//记录结果集
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
LinkedList<Integer> path = new LinkedList<>();
recursion(graph, 0, path);
return res;
}
//递归遍历图
private void recursion(int[][] graph, int s, LinkedList<Integer> path) {
//添加当前节点
path.add(s);
if (s == graph.length - 1) {
//到达终点 记录路径 注意此处要创建新的路径！！！
res.add(new LinkedList<>(path));
//移除最后添加的节点
path.removeLast();
//返回上一层
return;
}
//循环+递归添加邻居节点和其邻居节点（有向无环）
for (int v : graph[s]) {
recursion(graph, v, path);
}
//移除当前节点
path.removeLast();
}
}2、环检测算法及拓扑排序
207 题「课程表」
1、环检测算法（DFS 版本）
class Solution {
//判断节点是否已访问
boolean[] visited;
// 记录一次递归堆栈中的节点（也就是路径中的节点） 退出一层递归时需要移除节点
boolean[] onPath;
// 记录图中是否有环
boolean hasCycle = false;
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
visited = new boolean[numCourses];
onPath = new boolean[numCourses];
//每个节点都要遍历一次
for (int i = 0; i < numCourses; i++) {
recursion(graph, i);
}
return !hasCycle;
}
//递归遍历连接的节点
private void recursion(List<Integer>[] graph, int s) {
//路径中出现重复节点 表示已经成环
if (onPath[s]) {
hasCycle = true;
}
//如果已经成环 停止递归
if (hasCycle) {
return;
}
//如果已访问过 停止递归
if (visited[s]) {
return;
}
// 前序代码位置
visited[s] = true;
onPath[s] = true;
//从当前节点的邻接表数组中找到关联的节点
for (int v : graph[s]) {
recursion(graph, v);
}
// 后序代码位置 退出当前层时移除路径中的节点
onPath[s] = false;
}
//构建图的邻接表
private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
//构建图构建图的邻接表
List<Integer>[] graph = new LinkedList[numCourses];
//初始化邻接表
for (int i = 0; i < numCourses; i++) {
graph[i] = new LinkedList<>();
}
//取出依赖关系 也就是边
for (int[] edge : prerequisites) {
//取出边的两端顶点
int from = edge[1], to = edge[0];
//添加边
graph[from].add(to);
}
return graph;
}
}2、环检测算法（BFS 版本）
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
//构建图的邻接表
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
// 构建入度数组 存的是当前下标节点的入度
int[] indgree = new int[numCourses];
for (int[] e : prerequisites) {
//节点（下标）
int to = e[0];
//入度+1
indgree[to]++;
}
Queue<Integer> q = new LinkedList<>();
//将入度为0的节点放入队列
for (int i = 0; i < numCourses; i++) {
if (0 == indgree[i]) {
q.offer(i);
}
}
// 记录遍历的节点个数
int count = 0;
//弹出队列中的节点数据
while (!q.isEmpty()) {
count++;
//移除入度为0的节点
Integer cul = q.poll();
//BFS 宽度优先遍历，将指向的节点入度-1。。。graph[cul] 是cul指向的节点
for (int node : graph[cul]) {
indgree[node]--;
//如果入度也为0加入队列
if (0 == indgree[node]) {
q.offer(node);
}
}
}
//如果遍历过的个数等于节点数 那就是没环 否则就是有环
return count == numCourses;
}
private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new LinkedList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new LinkedList<>();
}
for (int[] e : prerequisites) {
int from = e[1], to = e[0];
graph[from].add(to);
}
return graph;
}
}210 题「课程表 II」
1、拓扑排序算法（DFS 版本）
class Solution {
boolean[] visited, onPath;
boolean hasCycle = false;
// 记录后序遍历结果
List<Integer> postorder = new ArrayList<>();
public int[] findOrder(int numCourses, int[][] prerequisites) {
//构建邻接表
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
visited = new boolean[numCourses];
onPath = new boolean[numCourses];
for (int i = 0; i < numCourses; i++) {
recursion(graph, i);
}
//成环时无法完成课程
if (hasCycle) {
return new int[]{};
}
//将后序遍历结果反过来
Collections.reverse(postorder);
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = postorder.get(i);
}
return res;
}
private void recursion(List<Integer>[] graph, int s) {
//节点已存在路径 时成环 退出
if (onPath[s]) {
hasCycle = true;
return;
}
//节点已访问过时退出
if (visited[s]) {
return;
}
visited[s] = true;
onPath[s] = true;
for (int v : graph[s]) {
recursion(graph, v);
}
onPath[s] = false;
//后序遍历位置 前面的课程都已经上完了
postorder.add(s);
}
private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new LinkedList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new LinkedList<>();
}
for (int[] e : prerequisites) {
int from = e[1], to = e[0];
graph[from].add(to);
}
return graph;
}
}2、拓扑排序算法（BFS 版本）
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
//构建图的邻接表
List<Integer>[] graph = buildGraph(numCourses, prerequisites);
//构建入度数组 存的是当前下标节点的入度
int[] indgree = new int[numCourses];
for (int[] e : prerequisites) {
//获取被指向的节点（下标）
int to = e[0];
//入度+1
indgree[to]++;
}
Queue<Integer> q = new LinkedList<>();
//将入度为0的节点放入队列
for (int i = 0; i < numCourses; i++) {
if (0 == indgree[i]) {
q.offer(i);
}
}
// 记录拓扑排序结果
int[] res = new int[numCourses];
// 记录遍历的节点个数
int count = 0;
//弹出队列中的节点数据 弹出顺序即为依赖顺序
while (!q.isEmpty()) {
//移除队列中（入度为0）的节点
Integer cur = q.poll();
res[count++] = cur;//记录顺序
//BFS 宽度优先遍历该节点指向的节点，将指向的节点入度-1。。。graph[cul] 是cul指向的节点
for (int node : graph[cur]) {
indgree[node]--;
//如果入度也为0加入队列
if (0 == indgree[node]) {
q.offer(node);
}
}
}
if (count != numCourses) {
// 存在环，拓扑排序不存在
return new int[]{};
}
return res;
}
private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new LinkedList[numCourses];
for (int i = 0; i < numCourses; i++) {
graph[i] = new LinkedList<>();
}
for (int[] e : prerequisites) {
int from = e[1], to = e[0];
graph[from].add(to);
}
return graph;
}
}3、二分图判定
二分图定义
785 题「判断二分图」
1、二分图判定DFS解法
//DFS
class Solution {
//存储是否访问 以及当前颜色的数组
boolean[] visited, color;
//结果
boolean ok = true;
public boolean isBipartite(int[][] graph) {
int l = graph.length;
visited = new boolean[l];
color = new boolean[l];
// 因为图不一定是联通的，可能存在多个子图
// 所以要把每个节点都作为起点进行一次遍历
// 如果发现任何一个子图不是二分图，整幅图都不算二分图
for (int i = 0; i < l; i++) {
//优化 已经访问过的节点就不必再次访问
if (!visited[i]) {
recursion(graph, i);
}
}
return ok;
}
private void recursion(int[][] graph, int i) {
// 如果已经确定不是二分图了，就不用浪费时间再递归遍历了
if (!ok) return;
visited[i] = true;
for (int e : graph[i]) {
if (!visited[e]) {
// 相邻节点 e 没有被访问过
// 那么应该给节点 e 涂上和节点 i 不同的颜色
color[e] = !color[i];
// 继续遍历 e
recursion(graph, e);
} else {
// 相邻节点 e 已经被访问过
// 根据 e 和 i 的颜色判断是否是二分图
if (color[e] == color[i]) {
// 若相同，则此图不是二分图
ok = false;
}
}
}
}
}2、二分图判定BFS解法
//BFS
class Solution {
//存储是否访问 以及当前颜色的数组
boolean[] visited, color;
//结果
boolean ok = true;
public boolean isBipartite(int[][] graph) {
int l = graph.length;
visited = new boolean[l];
color = new boolean[l];
// 因为图不一定是联通的，可能存在多个子图
// 所以要把每个节点都作为起点进行一次遍历
// 如果发现任何一个子图不是二分图，整幅图都不算二分图
for (int i = 0; i < l; i++) {
//优化 已经访问过的节点就不必再次访问
if (!visited[i]) {
BFS(graph, i);
}
}
return ok;
}
private void BFS(int[][] graph, int i) {
visited[i] = true;
Queue<Integer> queue = new LinkedList<>();
queue.offer(i);
while (!queue.isEmpty() && ok) {
Integer v = queue.poll();
for (int e : graph[v]) {
if (!visited[e]) {
visited[e] = true;
color[e] = !color[v];
queue.offer(e);
} else {
if (color[e] == color[v]) {
ok = false;
}
}
}
}
}
}886 题「可能的二分法」
DFS解法
class Solution {
boolean[] visited, color;
boolean ok = true;
public boolean possibleBipartition(int n, int[][] dislikes) {
visited = new boolean[n + 1];
color = new boolean[n + 1];
//构建邻接表
List<Integer>[] graph = buildGraph(n, dislikes);
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
recorsion(graph, i);
}
}
return ok;
}
private void recorsion(List<Integer>[] graph, int i) {
if (!ok) return;
visited[i] = true;
//遍历i的相邻节点
for (int v : graph[i]) {
if (!visited[v]) {
color[v] = !color[i];
recorsion(graph, v);
} else {
if (color[v] == color[i]) {
ok = false;
}
}
}
}
//构建邻接表
private List<Integer>[] buildGraph(int n, int[][] dislikes) {
List<Integer>[] graph = new LinkedList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new LinkedList<>();
}
for (int[] e : dislikes) {
int a = e[0], b = e[1];
// 「无向图」相当于「双向图」
graph[a].add(b);
graph[b].add(a);
}
return graph;
}
}BFS解法
class Solution1 {
boolean[] visited, color;
boolean ok = true;
public boolean possibleBipartition(int n, int[][] dislikes) {
visited = new boolean[n + 1];
color = new boolean[n + 1];
//构建邻接表
List<Integer>[] graph = buildGraph(n, dislikes);
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
BFS(graph, i);
}
}
return ok;
}
private void BFS(List<Integer>[] graph, int i) {
//访问到节点i
visited[i] = true;
Queue<Integer> queue = new LinkedList();
queue.offer(i);
//广度优先
while (!queue.isEmpty()) {
//如果已经不能了 就跳出循环
if (!ok) break;
//获取队列元素
int cul = queue.poll();
//遍历相邻节点
for (int n : graph[cul]) {
//相邻节点未访问 颜色赋予不同颜色
if (!visited[n]) {
visited[n] = true;
color[n] = !color[cul];
queue.offer(n);
} else {
//已访问 判断两者颜色是否相同 相同则不能划分二分图
if (color[n] == color[cul]) {
ok = false;
}
}
}
}
}
//构建邻接表
private List<Integer>[] buildGraph(int n, int[][] dislikes) {
List<Integer>[] graph = new LinkedList[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new LinkedList<>();
}
for (int[] e : dislikes) {
int a = e[0], b = e[1];
// 「无向图」相当于「双向图」
graph[a].add(b);
graph[b].add(a);
}
return graph;
}
}原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
