字符的全排列 // 题目链接-来源：力扣（LeetCode）输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例: 输入：s = “abc”输出：[“abc”,”acb”,”bac”,”bca”,”cab”,”cba”] 思路：求全排列，容易联想到 DFS 以及回溯算法。输入的字符构成一个集合，从集合中依次取出元素作为开始，进行DFS，剪枝：忽略遍历过的字符。对于输入字符的集合，我们可以用一个 StringBuilder 变量 res 来保存，这样我们可以按照索引指针每次「取」一个字符，同时也可以从 res 中删除该字符，完成回溯后再加回它，相当方便。取字符可以用一个 for 循环依次获取。为了防止结果出现重复，我们在 for 循环的同时维护一个 visited 集合，如果有相同字符，则会出现冲突，我们跳过该字符即可。在每一层的 DFS 当中，我们还需要一个 StringBuilder 变量 construct 来收集当前生成的字符串。相对应地，完成回溯后，要把当前收集的这个字符删除掉。DFS 跳出的条件就是 ...

二叉搜索树的中序遍历 // 题目链接-来源：力扣（LeetCode） 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 思路：要将BST的节点从小到大以循环双向链表串起来。注意BST的节点从小到大访问生成的序列即是中序遍历，所以我们可以以中序遍历为模板解决此题。我们需要用两个变量分别记录 中序遍历的当前节点 和 前驱节点。对于递归做法，用全局变量会比较方便，对于非递归做法，则用普通变量即可。我采用的是非递归做法，事实上，递归做法的代码会更加简洁明了。在遍历的同时调整 当前节点 和 前驱节点 的指针。注意，由于是循环链表，遍历完成后还要记得链接头节点和末尾节点。 时间复杂度：O(n)空间复杂度：O(n) 实现：1234567891011121314151617181920212223242526272829303132333435class Solution { public Node treeToDoublyList(Node root) { Stack<Node& ...

用哈希表建立索引 // 题目链接-来源：力扣（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)还有距离。考虑我们每入栈一个元素，对当前栈中「最小值」的影响。假设我们压入了一个元素并且是「最小值」，我们记录这个最小值。当我们后续压入任何大于这个值的元素，都对「最小值」没有影响。只有当这个元素出栈了，或者 ...