二叉树最大宽度
二叉树最大宽度给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在 32 位 带符号整数范围内。
示例 1：
123输入：root = [1,3,2,5,3,null,9]输出：4解释：最大宽度出现在树的第 3 层，宽度为 4 (5,3,null,9) 。
示例 2：
123输入：root = [1,3,2,5,null,null,9,6,null,7]输出：7解释：最大宽度出现在树的第 4 层，宽度为 7 (6,null,null,null,null,null,7) 。
示例 3：
123输入：root = [1,3,2,5]输出：2解释：最大宽度出现在树的第 2 层，宽度为 2 (3,2) 。
提示：
树中节点的数目范围是 [1, 3000]
-100 <= Node.val <= 100
...
二叉树的层序遍历
二叉树的层序遍历给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
12输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]]
示例 2：
12输入：root = [1]输出：[[1]]
示例 3：
12输入：root = []输出：[]
提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000
层序遍历需要借助队列
队列不为空时执行：
将根节点入队
获取队列长度size
如下行为重复size遍：
出队
如果有左孩子，左孩子入队
如果有右孩子，右孩子入队
size就是每一层的节点数，每次处理一层的节点
1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * Definition for a binary tree node. * public class TreeNode ...
对称二叉树
对称二叉树给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
12输入：root = [1,2,2,3,4,4,3]输出：true
示例 2：
12输入：root = [1,2,2,null,3,null,3]输出：false
提示：
树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
函数返回值：布尔类型
递归返回条件：两个节点至少有一个为空，如果相等返回true，如果不相等返回false
函数逻辑：如果两个节点的值相等，并且p的左子树等于q的右子树
123456789101112class Solution { public boolean isSymmetric(TreeNode root) { return check(root.left, root.right); } private boolean check(TreeNode p, TreeNode q) { if (p == null || q == ...
翻转二叉树
翻转二叉树给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
12输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1]
示例 2：
12输入：root = [2,1,3]输出：[2,3,1]
示例 3：
12输入：root = []输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100
递归三步走：
函数返回值：根节点
递归结束条件：root==null
执行逻辑：将左右孩子互换
123456789101112class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode left = invertTree(root.left); TreeNode right = inve ...
二叉树的最大深度
二叉树的最大深度给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
12输入：root = [3,9,20,null,null,15,7]输出：3
示例 2：
12输入：root = [1,null,2]输出：2
提示：
树中节点的数量在 [0, 104] 区间内。
-100 <= Node.val <= 100
写递归的三个步骤：
函数返回值：最大深度
递归返回条件：root为空
方法逻辑：返回左子树和右子树的最大值+1
为什么要+1？因为还需要加上根节点的长度
1
二叉树的中序遍历
二叉树的中序遍历给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
示例 1：
12输入：root = [1,null,2,3]输出：[1,3,2]
示例 2：
12输入：root = []输出：[]
示例 3：
12输入：root = [1]输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归写法
12345678910111213141516class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> list = new ArrayList<>(); mid(root, list); return list; } private void mid(TreeNode root, List list) ...
LRU缓存
LRU缓存请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
1234567891011121314151617输入["LRUCache", "put", "put", "get", "put", "get", "put", "get" ...
合并K个升序链表
合并K个升序链表给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
12345678910输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[ 1->4->5, 1->3->4, 2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6
示例 2：
12输入：lists = []输出：[]
示例 3：
12输入：lists = [[]]输出：[]
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4
方法一：遍历数组，两两合并lists[i-1]和lists[i]，将合并的结 ...
排序链表
排序链表给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
12输入：head = [4,2,1,3]输出：[1,2,3,4]
示例 2：
12输入：head = [-1,5,3,4,0]输出：[-1,0,3,4,5]
示例 3：
12输入：head = []输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
方法一，递归写法归并排序,空间复杂度logn
1234567891011121314151617181920212223242526272829303132333435363738394041class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { ...
随机链表的复制
随机链表的复制给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。
示例 1：
...