用哈希表建立索引 // 题目链接-来源：力扣（LeetCode） 请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 思路：原链表的每个 random 指针指向了一个随机节点的引用，对于我们新建的复制链表而言，这个引用的意义不大，关键是要找出这个节点对应的「序号」，我们才能在复制的链表当中按图索骥，建立一个相同的链接。给链表节点「标号」可以用哈希表完成，我们遍历原链表，对每个节点维护一个 <Node, Integer> 的映射，这个 Integer 就是节点的编号。同时遍历得到的节点值，我们拿来复制新的链表节点，记得用一个能快速索引的数据结构（可以用另一个哈希表，或者直接用一个节点数组ArrayList）帮助我们存储这些复制的节点，方便 ...

回溯，树的遍历 // 题目链接-来源：力扣（LeetCode） 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。 示例:给定如下二叉树，以及目标和 target = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1 返回: [ [5,4,11,2], [5,8,4,5]] 思路：回溯算法的经典应用。我们需要从根节点开始遍历整棵树，统计当前路径上的和，同时用一个列表记录当前经历过的节点，并与target作比较，如果相等，就在结果列表中记录这个列表。每个节点都有左右两个子树，利用DFS，我们可以先递归遍历左子树，但是当该子树的递归返回的时候，我们要剪除其相关信息，因为这对我们遍历右子树没有帮助，之后，我们再递归地遍历右子树。这就是「回溯」。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121 ...

树的后续遍历序列，BST // 题目链接-来源：力扣（LeetCode） 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树： 5 / \ 2 6 / 1 3示例 1： 输入: [1,6,3,2,5]输出: false 思路：二叉搜索树（BST）的特征是，中序序列一定是按从小到大顺序排列的。也就是说，对于由相同元素组成的二叉树，其中序序列是唯一确定的（当然我们不一定非要用某种方法-比如排序-来确定中序序列，只需要知道它是唯一的即可）。那么题目就简化成，知道中序序列，知道后序序列，我们可以唯一确定一棵二叉树，并判断其是否是BST。我们考虑后序序列的特点，「左、右、根」，当前子树的根节点一定位于当前子序列（即排除了父节点的剩余序列）的最后。而BST的特点是，根节点左子树的元素都小于根节点元素，右子树元素都大于根节点元素。综合以上两点，我们可以通过后序序列递归地确定一棵树的形状： 从尾部确定根节点 从后向前对剩余序列划分左右子树，先 ...

树的层序遍历 // 题目链接-来源：力扣（LeetCode） 请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7返回其层次遍历结果： [ [3], [20,9], [15,7]] 思路：此题与上一题类似，唯一的区别在于每一层需要变更一次打印的顺序。由于层序遍历限制了我们必须用队列来完成，容易想到可以方便从两端访问的数据结构就是双端队列 Deque。那么只要用一个标志记录当前层的遍历方向（从左往右，或是从右往左），即可完成题目的要求。这个标志可以是一个二元变量，每一层切换一次，也可以用当前层数的奇偶性直接判断。时间复杂度：O(n)空间复杂度：O(n) 实现：12345678910111213141516171819202122232425262728293031323334353637class Solution { ...

树的层序遍历，层次遍历 // 题目链接-来源：力扣（LeetCode） 从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7返回其层次遍历结果： [ [3], [9,20], [15,7]] 思路：这里的层次遍历不同于常规的层序遍历，需要每一层返回一组输出结果。也就是说，我们需要有某一种方法来记录当前所在的「深度」，或者记录当前行所需要打印的元素个数，以实现分批打印。这里我使用了递归的辅助方法，记录当前进行的「深度」，当深度超过列表行数时，新建列表，否则将元素插入当前最后一行列表的末尾。较简单的实现，可以在每一行打印开始前统计队列中元素个数，按此个数打印元素，即可省去每次都统计深度的麻烦。时间复杂度：O(n)空间复杂度：O(n) 实现：123456789101112131415161718192021222324252627class Solution { public List&l ...

树的层序遍历，BFS // 题目链接-来源：力扣（LeetCode） 从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。 例如:给定二叉树: [3,9,20,null,null,15,7], 3 / 9 20 / 15 7返回： [3,9,20,15,7] 思路：树的层序遍历，本质上是图的 BFS 算法。只需要借助一个队列即可实现。一开始入队根节点，之后循环从队列中弹出节点进行访问。对访问到的节点，打印后将左右子节点依次入队，循环操作即可完成遍历。时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617181920212223242526class Solution { public int[] levelOrder(TreeNode root) { Queue<TreeNode> q = new LinkedList<>(); List<Integer> output = new ...

栈的操作模拟 // 题目链接-来源：力扣（LeetCode） 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 示例 1： 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出：true解释：我们可以按以下顺序执行：push(1), push(2), push(3), push(4), pop() -> 4,push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1 思路：我们可以模拟入栈出栈操作，当我们成功模拟出出栈序列后，我们即可返回 true。 我们按照入栈序列，循环执行入栈操作，直到发生以下情况： 栈顶元素等于当前出栈序列指针指向的元素，那么我们就循环弹出栈顶元素并比较栈顶元素与出栈序列，直 ...

单调栈 // 题目链接-来源：力扣（LeetCode） 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。 示例: MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.min(); –> 返回 -3.minStack.pop();minStack.top(); –> 返回 0.minStack.min(); –> 返回 -2. 思路：此题的难点在于如何用尽可能低的复杂度实现对当前「最小元素」的查找。我们知道「最小堆」可以实现均摊复杂度为 O(logn) 的查找最小值的方式，距离我们要求的O(1)还有距离。考虑我们每入栈一个元素，对当前栈中「最小值」的影响。假设我们压入了一个元素并且是「最小值」，我们记录这个最小值。当我们后续压入任何大于这个值的元素，都对「最小值」没有影响。只有当这个元素出栈了，或者 ...

模拟矩阵路径进行遍历 // 题目链接-来源：力扣（LeetCode） 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5] 思路：由于矩阵形状相当规则，所以模拟顺时针方向遍历并不困难。关键点在于，决定何时转向，以及转向哪个方向，还有最终在何时停止。转向的时机：我们可以先判定当前前进方向上的下一个位置是否「可达」。首先需要维护一个同样大小的 visited[][] 矩阵，记录访问过的位置，若访问过，则「不可达」。另外，当下个位置发生数组越界时，同样不可达。这样我们只要在「不可达」时转向，「可达」时前进即可。方向确定：为了使代码简单，不至于对4个方向都做一次判断，我们可以维护一个类似时钟指针一样顺时针旋转的向量数组 directions[][]，这个数组里存储4个方向上的方向向量，例如， {0,1} 表示当前前进方向是上方。每次需要转向时，指针前进一位并对 4（数组长度） 求余即可进入下个方向。终止条件：我们可以计数输出的数字个数，当 ...

树的结构 // 题目链接-来源：力扣（LeetCode） 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。     1   /   2   2 / \ / 3  4 4  3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:     1   /   2   2   \      3    3 示例 1： 输入：root = [1,2,2,3,4,4,3]输出：true 思路：我们要判断镜像，关键在于找到每个节点应该比较的对象。对于任意两个节点 L 与 R，它们是否镜像取决于对应的子节点是否镜像，即 L.left 与 R.right， 还有 L.right 与 R.left是否镜像。于是我们可以这样递归地往下判定，直到最低层向上递归地返回判定结果。需要返回 false 的情况有 两节点不全为空 两节点均不空时值不相等 传递镜像位置子节点返回 false 判定。时间复杂度：O(n)空间复杂度：O(n) ...