吕小医's BLOG

剑指 Offer 33. 二叉搜索树的后序遍历序列题目12345678910111213141516171819202122输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。参考以下这颗二叉搜索树： 5 / \ 2 6 / \ 1 3示例 1：输入: [1,6,3,2,5]输出: false示例 2：输入: [1,3,2,6,5]输出: true 提示：数组长度 <= 1000 思路因为为后续遍历，所以一定满足，最后的节点一定是根节点，所以我们找到了根节点，然后因为这个树为二叉搜索树，所以根节点的左边的值一定小于根节点，右边的值一定大于根节点，所以我们在前面的数组中一定能找到left和right，如果这个数组不满足这个条件那么就一定不能构建成搜索树。 这样我们找到了left和right后依次类推，我们逐个判断left和right是不是二叉搜索树。 和剑指offer第七题类似，也是通过指针和前序中序后序遍历确定根节点 实现123456789101112 ...

剑指 Offer 35. 复杂链表的复制题目请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。 示例 1： 12输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]输出：[[7,null],[13,0],[11,4],[10,2],[1,0]] 示例 2： 12输入：head = [[1,1],[2,1]]输出：[[1,1],[2,1]] 示例 3： 12输入：head = [[3,null],[3,0],[3,null]]输出：[[3,null],[3,0],[3,null]] 示例 4： 123输入：head = []输出：[]解释：给定的链表为空（空指针），因此返回 null。 提示： ​ -10000 <= Node.val <= 10000​ Node.random 为空（null）或指向链表中的节点。​ 节点数目不超过 1000 。 思路本题的难点就 ...

剑指 Offer 38. 字符串的排列题目输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例: 12输入：s = "abc"输出：["abc","acb","bac","bca","cab","cba"] 限制： 1 <= s 的长度 <= 8 思路这个题有一个点： 不能有重复元素 这个不能有重复元素的意思是：数组中的一个字母只能有一次，但是可以给你重复的字母，所以我们不能用有一个hashset来判断这个元素是否已经加入（添加索引也不行，因为结果可能有重复） 12输入："aab"输出：["aba","aab","baa"] 所以我们可以通过递归的方法解决： 对于每一个元素，我们可以固定一个首部元素，然后对于后面的元素进行任意组合，然后后面的元素我们同样可以固定首部元素，对于后面的有元素进 ...

剑指 Offer 34. 二叉树中和为某一值的路径题目给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 示例 1： 12输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22输出：[[5,4,11,2],[5,8,4,5]] 示例 2： 12输入：root = [1,2,3], targetSum = 5输出：[] 示例 3： 12输入：root = [1,2], targetSum = 0输出：[] 思路深度遍历到根节点的时候判断最终值是否等于目标值，然后需要回溯 实现12345678910111213141516171819202122232425262728293031323334private static class Solution { LinkedList<List<Integer>> result = new LinkedList ...

剑指 Offer 37. 序列化二叉树题目请实现两个函数，分别用来序列化和反序列化二叉树。 你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。 提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。 示例： 12输入：root = [1,2,3,null,null,4,5]输出：[1,2,3,null,null,4,5] 思路层序遍历，然后在依次构建 实现12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970private static class Codec { // Encodes a tree to a ...

剑指 Offer 36. 二叉搜索树与双向链表题目输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。 特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。 思路这个题目的意思是，把一个二叉搜索树转化为一个链表，这个链表的顺序是从小到大的排序的双向环装链表。 这个样的话，我们可以先把这个节点进行一个中序遍历，中序遍历的结果就是一个顺序的 123456789// 打印中序遍历void dfs(Node root) { if(root == null) return; dfs(root.left); ...

剑指 Offer 39. 数组中出现次数超过一半的数字题目数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 12输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]输出: 2 限制： 11 <= 数组长度 <= 50000 注意：本题与主站 169 题相同：https://leetcode-cn.com/problems/majority-element/ 思路本题常见的三种解法： 哈希表统计法： 遍历数组 nums ，用 HashMap 统计各数字的数量，即可找出 众数 。此方法时间和空间复杂度均为 O(N)O(N) 。数组排序法： 将数组 nums 排序，数组中点的元素 一定为众数。摩尔投票法： 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)O(N) 和 O(1)O(1) ，为本题的最佳解法。 实现哈希表123456789101112131415161718192021222324252627private static class Solution & ...

剑指 Offer 32 - III. 从上到下打印二叉树 III题目123456789101112131415161718192021请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。例如:给定二叉树: [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其层次遍历结果：[ [3], [20,9], [15,7]] 提示：节点总数 <= 1000 思路在逐层打印的基础上加一个index%2； 实现123456789101112131415161718192021222324252627282930313233343536private static class Solution { public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) { ...

剑指 Offer 27. 二叉树的镜像题目1234567891011121314151617181920212223242526请完成一个函数，输入一个二叉树，该函数输出它的镜像。例如输入：     4   /   \  2     7 / \   / \1   3 6   9镜像输出：     4   /   \  7     2 / \   / \9   6 3   1 示例 1：输入：root = [4,2,7,1,3,6,9]输出：[4,7,2,9,6,3,1] 限制：0 <= 节点个数 <= 1000 思路我们可以在原来的数组上进行转换，寻找子问题，我们可以先转换叶子节点，然后逐层向根节点转换。这就是典型的递归的思维 实现1234567891011private static class Solution { public TreeNode mirrorTree(TreeNode root) { if (root == null){ return null; } ...

剑指 Offer 24. 反转链表题目123456789定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。示例:输入: 1->2->3->4->5->NULL输出: 5->4->3->2->1->NULL 限制：0 <= 节点个数 <= 5000 思路双指针，pre表示上一个节点，cur表示当前节点，temp表示下一个节点 实现1234567891011121314private static class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { ListNode temp = cur.next; cur.next = pre; pre = cur; ...

剑指 Offer 25. 合并两个排序的链表题目12345678910输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。示例1：输入：1->2->4, 1->3->4输出：1->1->2->3->4->4限制：0 <= 链表长度 <= 1000 思想双指针，声明一个变量记录新链表中的最大值，对每一个链表声明一个指针，先比较这两个指针中的值，小的值追加到新链表后指针++ 实现1234567891011121314151617181920212223242526272829303132333435363738private static class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { ...

剑指 Offer 26. 树的子结构题目123456789101112131415161718192021222324252627282930输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)B是A的子结构， 即 A中有出现和B相同的结构和节点值。例如:给定的树 A:     3    / \   4   5  / \ 1   2给定的树 B：   4   / 1返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。示例 1：输入：A = [1,2,3], B = [3,1]输出：false示例 2：输入：A = [3,4,5,1,2], B = [4,1]输出：true限制：0 <= 节点个数 <= 10000 思路深度遍历每一个节点，对每一个节点都对比一次TreeB，所以需要两个函数，第一个就是dfs，第二个就是对比TreeA和TreeB 实现123456789101112131415161718192021private static class Solution { public boolean is ...

剑指 Offer 28. 对称的二叉树题目123456789101112131415161718192021222324252627请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，二叉树 [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示例 2：输入：root = [1,2,2,null,3,null,3]输出：false 限制：0 <= 节点个数 <= 1000 思路层序遍历，拿到每一层的数据，然后写一个函数判断这一层的数字是否为中心对称。 实现拿到每一层的数据然后判断，效率太低，击败了5%的用户 1234567891011121314151617181920212223242526272829303132333435363738394 ...

剑指 Offer 29. 顺时针打印矩阵题目1234567891011121314151617输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1：输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[1,2,3,6,9,8,7,4,5]示例 2：输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]输出：[1,2,3,4,8,12,11,10,9,5,6,7] 限制：0 <= matrix.length <= 1000 <= matrix[i].length <= 100 思路定义四个指针，分别为top，right、bottom、left，能够确定四个角的位置，然后逐层遍历 每次打印完一层后都要判断数组是否发生越界（已经不用打印了） 实现通过定义的四个变量来判断是否越界 1234567891011121314151617181920212223242526272829303132333435363738394041424344private static class Sol ...

剑指 Offer 30. 包含min函数的栈题目123456789101112131415161718定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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. 提示：各函数的调用总次数不超过 20000 次 思路这道题需要注意的是： min方法：获取栈中的最小数但是这个数不会弹出栈 top方法：获取栈顶元素，这个数不会弹出栈 push方法：向栈中放入元素 pop方法：弹出栈顶元素 关键就是min方法，因为要min方法为O(1)，所以我们必须存放min的那个数据结构，我们另外使用一个栈存放这个min， ...