# /
# 一些术语
# 循环、遍历、迭代
循环while/for指重复执行一段代码。（递归、遍历、迭代都是循环。）遍历for/foreach指重复执行一段代码来访问集合的每个元素。迭代iterate指重复执行迭代器iterator.下代next来访问集合的每个元素。迭代器iterator规定实现下代next，无规定实现游标cursor、索引index。
# 链表
# 环形链表q141简单
题目来源：141. 环形链表 - 力扣（LeetCode） (opens new window)
题干：判断链表是否存在环。
题解要点：
1、遍历链表，某个节点重复出现说明存在环。
2、通过哈希表判断是否重复出现。
# 两数相加q2中等
题目来源：2. 两数相加 - 力扣（LeetCode） (opens new window)
题干：两个链表的节点值相加为一个新链表。
题解要点：
1、同时遍历两个链表，节点值相加放入新链表。
2、两个个位数相加可能是一个十位数，个位放在当前节点、十位放在下一节点。
# 合并两个有序链表q21简单
题目来源：21. 合并两个有序链表 - 力扣（LeetCode） (opens new window)
题干：将两个升序链表合并为一个新的升序链表。
题解要点：
1、同时遍历两个链表，比较节点值，先放入小值再放入大值。
# 随机链表的复制q138中等
题目来源：138. 随机链表的复制 - 力扣（LeetCode） (opens new window)
题干：深拷贝复制链表。
题解要点：
1、通过next直接遍历链表。直接拷贝val，放到哈希表中。
2、继续，通过next直接遍历链表。处理node.next，直接在哈希表中查找node.next，即可知道新节点的node.next是哪个。
3、继续，通过next直接遍历链表。处理node.random，直接在哈希表中查找node.random，即可知道新节点的node.random是哪个。
# 反转链表IIq92中等
题目来源：92. 反转链表 II - 力扣（LeetCode） (opens new window)
题干：链表反转。
题解要点：
1、子链表的前置节点（也称虚拟头节点）。
2、链表反转函数。
//反转链表
private void reverseLinkedList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
}
2
3
4
5
6
7
8
9
10
11
12
# K个一组翻转链表q25困难
题目来源：25. K 个一组翻转链表 - 力扣（LeetCode） (opens new window)
题干：链表反转。
题解要点：
1、子链表的前置节点（也称虚拟头节点）。
2、链表反转函数。
//链表的翻转，主要依赖这个翻转函数。
//反转链表，返回头尾节点
public ListNode[] myReverse(ListNode head, ListNode tail) {
ListNode pre = null;//缓存pre//tail.next;
ListNode cur = head;
//while (cur != null) {
while (pre != tail) {
ListNode next = cur.next;//缓存next
cur.next = pre;//head.next指向pre（反转）
pre = cur;
cur = next;//处理下一节点
}
return new ListNode[]{tail, head};
}
2
3
4
5
6
7
8
9
10
11
12
13
14
# 删除链表的倒数第N个结点q19中等
题目来源：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） (opens new window)
题干：删除第N个节点。
题解要点：1、删除当前节点。
cur.next = cur.next.next;//删除第N个节点
# 删除排序链表中的重复元素IIq82中等
题目来源：82. 删除排序链表中的重复元素 II - 力扣（LeetCode） (opens new window)
题干：连续删除节点。
题解要点：1、删除“有序链表”的重复元素，说明重复元素是连续的。
if (cur.next.val == cur.next.next.val) {
//连续删除重复元素
int x = cur.next.val;
while (cur.next != null && cur.next.val == x) {
cur.next = cur.next.next;
}
}
2
3
4
5
6
7
# 旋转链表q61中等
题目来源：61. 旋转链表 - 力扣（LeetCode） (opens new window)
题干：旋转链表。
题解要点：
1、旋转链表指把链表看成一个环。旋转一次，所有节点右移一位。
2、遍历拿到尾节点，连上头节点，形成环。
3、形成环后，遍历拿到新的头节点。
4、遍历拿到新的尾节点，断开环。
# 分隔链表q86中等
题目来源：86. 分隔链表 - 力扣（LeetCode） (opens new window)
题干：链表重组。
题解要点：遍历链表，找出x的大小值。
# LRU（最近最少使用）缓存q146中等
题目来源：146. LRU 缓存 - 力扣（LeetCode） (opens new window)
题干：热留存（排头），冷淘汰（删尾）。
题解要点：
1、每次使用get后，要移动到链表头。
2、每次使用put后，要添加到链表头。如果链表满，还要删除链表尾。
# 二叉树
# 二叉树的最大深度q104简单
题目来源：104. 二叉树的最大深度 - 力扣（LeetCode） (opens new window)
题干：二叉树深度。
题解要点：
1、根树深度=1+最大值(左子树深度,右子树深度)。
2、叶子树深度=0。
3、满足递归条件。
# 相同的树q100简单
题目来源：100. 相同的树 - 力扣（LeetCode） (opens new window)
题干：同时遍历两个树，比较。
题解要点：
# 深度优先搜索（递归）：
1、根树相同=左子树相同&右子树相同。
2、叶子树是否相同是明确的。
3、满足递归条件。
# 广度优先搜索（迭代）：
1、双队列（先进先出），横向顺序放入队列。
2、一一比较。
# 翻转二叉树q226简单
题目来源：226. 翻转二叉树 - 力扣（LeetCode） (opens new window)
题干：遍历树，翻转。
题解要点：
# 深度优先搜索（递归）：
1、子树翻转，则根树翻转。
2、子树翻转是明确的。
3、满足递归条件。
# 广度优先搜索（迭代）：
1、队列（先进先出），横向顺序放入队列
2、一一翻转。
TreeNode tmp = queue.poll();
TreeNode left = tmp.left;
tmp.left = tmp.right;
tmp.right = left;
2
3
4
# 对称二叉树q101简单
题目来源：101. 对称二叉树 - 力扣（LeetCode） (opens new window)
题干：同时遍历两个树，比较。
题解要点：
# 深度优先搜索（递归）：
1、子树相等，则根树相等。
2、子树是否相等是明确的。
3、满足递归条件。
# 广度优先搜索（迭代）：
1、队列（先进先出），横向顺序放入队列。
2、一一比较。
# 从前序与中序遍历序列构造二叉树q105中等
题目来源：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode） (opens new window)
题干：前中序反推二叉树节点。
题解要点：
# 特殊深度优先搜索（递归）：
1、前序遍历，可得根节点。
2、根节点+中序遍历，可得左右子节点。
//这个“构建树方法”是，通过准确的拿到“前序遍历”的根节点位置与左右子节点位置构造出来的。
//所以找到“前序遍历”的根节点位置与左右子节点位置，就是题解。
//（解题时会发现，“前序遍历”的左右子树边界位置，难以确定。必须借助“中序遍历”根节点位置与左子树边界位置才能确定。）
# 广度优先搜索（迭代）：
这个逻辑可读性差，忽略。
1、“前序遍历”中，[根节点,左子树,右子树]。 2、“中序遍历”中，[左子树,根节点,右子树]。 3、遍历“前序遍历”与“中序遍历”，把“前序遍历”压入栈中， 4、如果
“前序遍历”栈顶≠“中序遍历”最左说明没有来到“前序遍历”的左子树的左右节点边界。 5、如果“前序遍历”栈顶=“中序遍历”最左说明来到“前序遍历”的左子树的左右节点边界+1，即来到“前序遍历”的左子树的右节点。 （注意：这里“前序遍历”弹栈与“中序遍历”右移一一比较，相当于“前序遍历”左子树与“中序遍历”左子树反方向一一比较，这样可以判断节点是“前序遍历”左子树中的左节点还是右节点。相同是左节点，不同是右节点。） 6、手写这个逻辑较难。
# 从中序与后序遍历序列构造二叉树q106中等
题目来源：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode） (opens new window)
题干：中后序反推二叉树节点。
题解要点：
同上。
# 填充每个节点的下一个右侧节点指针IIq117中等
题目来源：117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode） (opens new window)
题干：二叉树的每个节点新增一个水平指针next。
题解要点：
# 广度优先搜索（迭代）：
1、这个题的难点是“怎么一层层处理水平层的节点？”。
从第一层开始遍历树，把水平层节点放入队列中，并处理next指针。
2、“怎么确定是每一层的头节点、尾节点？”
# 二叉树展开为链表q114中等
题目来源：114. 二叉树展开为链表 - 力扣（LeetCode） (opens new window)
题干：二叉树重组。
题解要点：
# 深度优先搜索（递归）：
1、题中的二叉树是以前序序列的方式存放。
2、以前序遍历遍历树，同时放入数组中。
3、从数组取出节点，并更新左右指针，形成链表（单边树）。
# 路径总和q112简单
题目来源：112. 路径总和 - 力扣（LeetCode） (opens new window)
题干：统计二叉树根路径。
题解要点：
# 广度优先搜索（迭代）：
1、到达当前节点的路径总和=当前节点值+所有父节点值。
# 求根节点到叶节点数字之和q129中等
题目来源：129. 求根节点到叶节点数字之和 - 力扣（LeetCode） (opens new window)
题干：统计二叉树根路径数字。
题解要点：
# 深度优先搜索（递归）：
深度优先搜索是很直观的做法。从根节点开始，遍历每个节点，如果遇到
叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。
1、在深度优先遍历树的过程中，累加节点值。
# 广度优先搜索（迭代）：
1、使用广度优先搜索，需要维护两个队列，分别存储节点和节点对应的数字。 2、初始时，将根节点和根节点的值分别加入两个队列。
每次从两个队列分别取出一个节点和一个数字，进行如下操作： （1）如果当前节点是叶子节点，则将该节点对应的数字加到数字之和； （2）如果当前节点不是叶子节点，则获得当前节点的非空子节点，并根据当前节点对应的数字和子节点的值计算子节点对应的数字，然后将子节点和子节点对应的数字分别加入两个队列。 （每次把左右节点放入队列，再从队列取出第一个，则取出的节点是水平优先的。） 3、搜索结束后，即可得到所有叶子节点对应的数字之和。）
1、在广度优先遍历树的过程中，通过“值队列”存放累加节点值。
# 二叉树中的最大路径和q124困难
题目来源：124. 二叉树中的最大路径和 - 力扣（LeetCode） (opens new window)
题干：统计二叉树路径。
题解要点：
# 深度优先搜索（递归）：
1、不能直接递归：当前节点的最大路径≠左右子节点的最大路径。
2、当前节点的最大路径=自己+当前节点到叶子节点最大值(左节点)+当前节点到叶子节点最大值(右节点)。
# 二叉搜索树迭代器q173中等
题目来源：173. 二叉搜索树迭代器 - 力扣（LeetCode） (opens new window)
题干：遍历二叉树。
题解要点：
# 深度优先搜索（递归）：
直接对二叉搜索树做一次完全的递归遍历，获取
中序遍历的全部结果并保存在数组中。随后，我们利用得到的数组本身来实现迭代器。
1、题干要求输入前序序列输出中序序列(升序序列)。
2、所以，递归遍历二叉树时，中序序列(升序序列)放入数组。迭代器next取出时，为中序遍历。
# 广度优先搜索（迭代）：
除了递归的方法外，我们还可以利用栈这一数据结构，通过迭代的方式对二叉树做中序遍历。此时，我们无需预先计算出中序遍历的全部结果，只需要实时维护当前栈的情况即可。
1、题干要求输入前序序列输出中序序列(升序序列)。
2、所以迭代器next时，先中序序列(升序序列)放入栈，再出栈，即为中序遍历。
# 完全二叉树的节点个数q222简单
题目来源：222. 完全二叉树的节点个数 - 力扣（LeetCode） (opens new window)
题干：遍历二叉树。
完全二叉树：在完全二叉树中，除了
最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
题解要点：
# 深度优先搜索（递归）：
1、当前树的节点个数=自己一个+左右子树的节点个数。
2、子树的节点个数是明确的。
3、满足递归条件。
# 二叉树的最近公共祖先q236中等
题目来源：236. 二叉树的最近公共祖先 - 力扣（LeetCode） (opens new window)
题干：遍历二叉树。
公共祖先：在树中的节点p、q的共同祖先节点x（每个节点都是它自己的祖先）。 最近公共祖先：节点x的深度尽可能大。节点p、q与节点x的距离尽可能小。
题解要点：
# 深度优先搜索（递归）：
1、不能直接递归：当前节点是p与q的祖先≠左、右节点是p与q的祖先。
2、当前节点是p或q的祖先=左、右、自己节点是p或q其中1个。
3、在递归的过程中，记录最近公共祖先。（这个判断逻辑其实比较难想到。）
if (isLeft && isRight) {
ans = root;
} else if (isSelf(root, p, q) && (isLeft || isRight)) {//自己是其中1个 && 左、右是其中1个
ans = root;
}
2
3
4
5
# 存储父节点（递归）：
1、每个节点只有一个父节点，递归遍历树把每个节点的父节点保存到哈希表。
2、迭代p的父节点，得到p的全部祖先节点。保存到哈希表。
3、得到p、q的全部祖先节点，得解。
← 一些面试题