剑指Offer题集（力扣）

慈云数据 2024-03-15 技术支持 60 0

文章目录

剑指Offer题集（[力扣题单](https://leetcode.cn/problemset/all/?listId=lcof&page=1)）
- [剑指 Offer 03. 数组中重复的数字](https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)
- [剑指 Offer 04. 二维数组中的查找](https://leetcode.cn/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/)
- [剑指 Offer 05. 替换空格](https://leetcode.cn/problems/ti-huan-kong-ge-lcof/)
- [剑指 Offer 06. 从尾到头打印链表](https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)
- 🎃[剑指 Offer 07. 重建二叉树[前序+中序]](https://leetcode.cn/problems/zhong-jian-er-cha-shu-lcof/)
- - 106.重建二叉树[后序+中序]
  - [889. 根据前序和后序遍历构造二叉树](https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-postorder-traversal/)
  - [剑指 Offer 09. 用两个栈实现队列](https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)
  - [剑指 Offer 10- I. 斐波那契数列](https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/)
  - [剑指 Offer 10- II. 青蛙跳台阶问题【爬楼梯】](https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/)
  - [剑指 Offer 11. 旋转数组的最小数字](https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/)
  - [剑指 Offer 12. 矩阵中的路径](https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/)
  - [剑指 Offer 13. 机器人的运动范围](https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/)
  - 🎉[剑指 Offer 14- I. 剪绳子](https://leetcode.cn/problems/jian-sheng-zi-lcof/)
  - [剑指 Offer 14- II. 剪绳子 II](https://leetcode.cn/problems/jian-sheng-zi-ii-lcof/)
  - [剑指 Offer 15. 二进制中1的个数](https://leetcode.cn/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/)
  - [剑指 Offer 16. 数值的整数次方](https://leetcode.cn/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/)
  - [剑指 Offer 17. 打印从1到最大的n位数](https://leetcode.cn/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/)
  - [剑指 Offer 18. 删除链表的节点](https://leetcode.cn/problems/shan-chu-lian-biao-de-jie-dian-lcof/)
  - 🎉[剑指 Offer 19. 正则表达式匹配](https://leetcode.cn/problems/zheng-ze-biao-da-shi-pi-pei-lcof/)
  - [剑指 Offer 20. 表示数值的字符串](https://leetcode.cn/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof/)
  - [剑指 Offer 21. 调整数组顺序使奇数位于偶数前面](https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/)
  - [剑指 Offer 22. 链表中倒数第k个节点](https://leetcode.cn/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)
  - [剑指 Offer 24. 反转链表](https://leetcode.cn/problems/fan-zhuan-lian-biao-lcof/)
  - [剑指 Offer 25. 合并两个排序的链表](https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/)
  - 🎉[剑指 Offer 26. 树的子结构](https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/)
  - [剑指 Offer 27. 二叉树的镜像](https://leetcode.cn/problems/er-cha-shu-de-jing-xiang-lcof/)
  - [剑指 Offer 28. 对称的二叉树](https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/)
  - [剑指 Offer 29. 顺时针打印矩阵](https://leetcode.cn/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/)
  - [剑指 Offer 30. 包含min函数的栈](https://leetcode.cn/problems/bao-han-minhan-shu-de-zhan-lcof/)
  - [剑指 Offer 31. 栈的压入、弹出序列](https://leetcode.cn/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof/)
  - [剑指 Offer 32 - I. 从上到下打印二叉树](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/)
  - [剑指 Offer 32 - II. 从上到下打印二叉树 II](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/)
  - [剑指 Offer 32 - III. 从上到下打印二叉树 III](https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/)
  - 🎃[剑指 Offer 33. 二叉搜索树的后序遍历序列](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/)
  - [剑指 Offer 34. 二叉树中和为某一值的路径](https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/)
  - [剑指 Offer 35. 复杂链表的复制](https://leetcode.cn/problems/fu-za-lian-biao-de-fu-zhi-lcof/)
  - 🎃[剑指 Offer 36. 二叉搜索树与双向链表](https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/)
  - 🎉[剑指 Offer 37. 序列化二叉树](https://leetcode.cn/problems/xu-lie-hua-er-cha-shu-lcof/)
  - [剑指 Offer 38. 字符串的排列](https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof/)
  - [剑指 Offer 39. 数组中出现次数超过一半的数字](https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/)
  - [剑指 Offer 40. 最小的k个数](https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/)
  - 🎉[剑指 Offer 41. 数据流中的中位数](https://leetcode.cn/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/)
  - [剑指 Offer 42. 连续子数组的最大和](https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/)
  - 🎉[剑指 Offer 43. 1～n 整数中 1 出现的次数](https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/)【数位DP】
  - 🎃[剑指 Offer 44. 数字序列中某一位的数字](https://leetcode.cn/problems/shu-zi-xu-lie-zhong-mou-yi-wei-de-shu-zi-lcof/)
  - 🎃[剑指 Offer 45. 把数组排成最小的数](https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/)
  - [剑指 Offer 46. 把数字翻译成字符串](https://leetcode.cn/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/)
  - [剑指 Offer 47. 礼物的最大价值](https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof/)
  - [剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/)
  - 🎉[剑指 Offer 49. 丑数](https://leetcode.cn/problems/chou-shu-lcof/)
  - [剑指 Offer 50. 第一个只出现一次的字符](https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/)
  - 🎉[剑指 Offer 51. 数组中的逆序对](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)
  - 💕[剑指 Offer 52. 两个链表的第一个公共节点](https://leetcode.cn/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)
  - [剑指 Offer 53 - I. 在排序数组中查找数字 I](https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/)
  - [剑指 Offer 53 - II. 0～n-1中缺失的数字](https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/)
  - [剑指 Offer 54. 二叉搜索树的第k大节点](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/)
  - [剑指 Offer 55 - I. 二叉树的深度](https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/)
  - [剑指 Offer 55 - II. 平衡二叉树](https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/)
  - 🎃[剑指 Offer 56 - I. 数组中数字出现的次数](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/)
  - [剑指 Offer 56 - II. 数组中数字出现的次数 II](https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/)
  - [剑指 Offer 57. 和为s的两个数字](https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof/)
  - [剑指 Offer 57 - II. 和为s的连续正数序列](https://leetcode.cn/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/)
  - [剑指 Offer 58 - I. 翻转单词顺序](https://leetcode.cn/problems/fan-zhuan-dan-ci-shun-xu-lcof/)
  - [剑指 Offer 58 - II. 左旋转字符串](https://leetcode.cn/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)
  - 🎉[剑指 Offer 59 - I. 滑动窗口的最大值](https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/)
  - 🎃[剑指 Offer 59 - II. 队列的最大值](https://leetcode.cn/problems/dui-lie-de-zui-da-zhi-lcof/)
  - 🎃[剑指 Offer 60. n个骰子的点数](https://leetcode.cn/problems/nge-tou-zi-de-dian-shu-lcof/)
  - [剑指 Offer 61. 扑克牌中的顺子](https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/)
  - 🎃[剑指 Offer 62. 圆圈中最后剩下的数字](https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/)
  - 🎉[剑指 Offer 63. 股票的最大利润](https://leetcode.cn/problems/gu-piao-de-zui-da-li-run-lcof/) + 拓展问题
  - [剑指 Offer 64. 求1+2+…+n](https://leetcode.cn/problems/qiu-12n-lcof/)
  - [剑指 Offer 65. 不用加减乘除做加法](https://leetcode.cn/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/)
  - [剑指 Offer 66. 构建乘积数组](https://leetcode.cn/problems/gou-jian-cheng-ji-shu-zu-lcof/)
  - 🎃[剑指 Offer 67. 把字符串转换成整数](https://leetcode.cn/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/)
  - [剑指 Offer 68 - I. 二叉搜索树的最近公共祖先](https://leetcode.cn/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/)
  - [剑指 Offer 68 - II. 二叉树的最近公共祖先](https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/)
    剑指Offer题集（力扣题单）
    
    剑指 Offer 03. 数组中重复的数字
    
    难度简单1155
    
    找出数组中重复的数字。
    
    在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
    
    示例 1：
```
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3 
```
    限制：
```
2 
    public int findRepeatNumber(int[] nums) {
        Set
            if(set.contains(num)) return num;
            set.add(num);
        }
        return -1;
    }
}

    // 鸽巢原理，因为出现的元素值 2->3->4->4
```
    限制：
```
0  ListNode:
        # 递归边界：两个链表有一个是空的
        if not l1: # l1为空
            return l2
        if not l2:
            return l1
        pre = None
        # 两个链表头部值较小的一个节点与剩下元素的 merge 操作结果合并
        if l1.val  
🎉剑指 Offer 26. 树的子结构 
难度中等741 
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) 
B是A的子结构， 即 A中有出现和B相同的结构和节点值。 
示例 1： 
输入：A = [1,2,3], B = [3,1]
输出：false
 
示例 2： 
输入：A = [3,4,5,1,2], B = [4,1]
输出：true
 
限制： 
0 
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null)
            return false;
        return hasSubStructure(A, B) || isSubStructure(A.left, B)
            || isSubStructure(A.right, B);
    }
    public boolean hasSubStructure(TreeNode A, TreeNode B){
        if(B == null)
            return true;
        if(A == null || A.val != B.val)
            return false;
        return hasSubStructure(A.left, B.left) && hasSubStructure(A.right, B.right);
    }
}
hr / 
pre class="brush:python;toolbar:false"class Solution:
    def isSubStructure(self, A: TreeNode, B: TreeNode) - bool:
        # 注意区分子结构和子树 572. 另一棵树的子树
        if not A or not B:
            return False
        return self.hasSubStructure(A, B) or \
                self.isSubStructure(A.left, B) or \
                self.isSubStructure(A.right, B)
    
    def hasSubStructure(self, A, B: TreeNode) -> bool:
        if not B:
            return True
        if not A or A.val != B.val:
            return False
        return self.hasSubStructure(A.left, B.left) and \
                self.hasSubStructure(A.right, B.right)
```
    剑指 Offer 27. 二叉树的镜像
    
    难度简单354
    
    请完成一个函数，输入一个二叉树，该函数输出它的镜像。
    
    例如输入：
    
    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  bool:
        def check(node1, node2: TreeNode) -> bool:
            if not node1 and not node2:
                return True
            if not node1 or not node2:
                return False
            return node1.val == node2.val and \
                    check(node1.left, node2.right) and \
                    check(node1.right, node2.left)
        
        if not root:
            return True
        return check(root, root)
```
    剑指 Offer 29. 顺时针打印矩阵
    
    难度简单528
    
    输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
    
    示例 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 if len(matrix) == 0 { return make([]int, 0) } l := 0 r := len(matrix[0])-1 t := 0 b := len(matrix)-1 res := make([]int, (r+1) * (b+1)) x := 0 for { for i := l; i res[x] = matrix[t][i] x++ } t++ if t b {break} for i := t; i res[x] = matrix[i][r] x++ } r-- if l r {break} for i := r; i = l; i-- { res[x] = matrix[b][i] x++ } b-- if t b {break} for i := b; i = t; i-- { res[x] = matrix[i][l] x++ } l++ if l r {break} } return res }
      剑指 Offer 30. 包含min函数的栈
      
      难度简单492
      
      定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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.
```
      提示：
      1. 各函数的调用总次数不超过 20000 次
      题解：
      
      维护一个栈，保存当前栈顶元素和栈中最小元素值
```
class MinStack:
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.st = [] # 当前栈顶元素，栈中最小元素值
    def push(self, x: int) -> None:
        if len(self.st) == 0:
            self.st.append((x, x))
            return
        _, m = self.st[-1]
        if m > x: m = x
        self.st.append((x, m))
        return
    def pop(self) -> None:
        self.st.pop()
    def top(self) -> int:
        return self.st[-1][0]
    def min(self) -> int:
        return self.st[-1][1]
```
      剑指 Offer 31. 栈的压入、弹出序列
      
      难度中等443
      
      输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {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
```
      示例 2：
```
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
```
      提示：
      1. 0 List[int]: res = [] if not root: return res q = collections.deque() q.append(root) while q: size = len(q) while size > 0: node = q.pop() res.append(node.val) if node.left: q.appendleft(node.left) if node.right: q.appendleft(node.right) size -= 1 return res
        剑指 Offer 32 - II. 从上到下打印二叉树 II
        
        难度简单288
        
        从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
        
        例如:
        给定二叉树: [3,9,20,null,null,15,7],
        
        3 / \ 9 20 / \ 15 7
        
        返回其层次遍历结果：
        
        [ [3], [9,20], [15,7] ]
        
        提示：
        
        节点总数 List[List[int]]: res = [] if not root: return res q = [root] while q: nxt = [] tmp = [] for node in q: tmp.append(node.val) if node.left: nxt.append(node.left) if node.right: nxt.append(node.right) res.append(tmp) q = nxt return res
        剑指 Offer 32 - III. 从上到下打印二叉树 III
        
        难度中等285
        
        请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
        
        例如:
        给定二叉树: [3,9,20,null,null,15,7],
        
        3 / \ 9 20 / \ 15 7
        
        返回其层次遍历结果：
        
        [ [3], [20,9], [15,7] ]
        
        提示：
        
        节点总数 List[List[int]]: res = [] if not root: return res q = [root] depth = 0 while q: nxt = [] tmp = [] depth += 1 for node in q: tmp.append(node.val) if node.left: nxt.append(node.left) if node.right: nxt.append(node.right) if depth % 2 == 0: tmp.reverse() res.append(tmp) q = nxt return res
        🎃剑指 Offer 33. 二叉搜索树的后序遍历序列
        
        难度中等719
        
        输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
        
        参考以下这颗二叉搜索树：
        
        5 / \ 2 6 / \ 1 3
        
        示例 1：
        
        输入: [1,6,3,2,5] 输出: false
        
        示例 2：
        
        输入: [1,3,2,6,5] 输出: true
        
        提示：
        
        数组长度 bool: if len(postorder) == 0: return True def verify(left, right: int) -> bool: if left >= right: return True # 因为数组中最后一个值postorder[right]是根节点，这里从左往右找出第一个比根节点大的值， # 他后面的都是根节点的右子节点（包含当前值，不包含最后一个值，因为最后一个是根节点），他前面的都是根节点的左子节点 mid = left root = postorder[right] while postorder[mid]
        方法二：栈
        
        关于if (cur > parent) return false; 的思考
        
        三个前提
        
        1.两个数如果arr[i]
        2.如果arr[i]>arr[i+1]，那么arr[i+1]一定是arr[0]……arr[i]中某个节点的左孩子，并且这个值是大于arr[i+1]中最小
        
        3.递增栈
        
        当遇到一个值a小于栈顶值时，需要找到该值的父节点b(即栈内最早压栈的且大于该值的值)
        
        找到该值b以后作为parent值, a为b的左孩子
        
        后续再遇到值x，有如下情况：
        
        1.它是栈内某个值的左孩子，那么该值肯定小于等于栈顶值a，(递增栈，栈顶最大)–>x
        2.它是栈顶值a的右孩子,但是a是b的左孩子，因此它的孩子值也不能大于b --> x bool: st = [] fa = inf for i, cur in enumerate(postorder[::-1]): # 注意for循环是倒叙遍历的 # 当如果当前节点小于栈顶元素，说明栈顶元素和当前值构成了倒叙， # 说明当前节点是前面某个节点的左子节点，我们要找到他的父节点 while st and st[-1] > cur: fa = st.pop() # 只要遇到了某一个左子节点，才会执行上面的代码，才会更新parent的值，否则parent就是一个非常大的值， # 也就是说如果一直没有遇到左子节点，那么右子节点可以非常大 if cur > fa: return False st.append(cur) return True
        剑指 Offer 34. 二叉树中和为某一值的路径
        
        难度中等421
        
        给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有从根节点到叶子节点路径总和等于给定目标和的路径。
        
        叶子节点是指没有子节点的节点。
        
        示例 1：
        
        输入：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：
        
        输入：root = [1,2,3], targetSum = 5 输出：[]
        
        示例 3：
        
        输入：root = [1,2], targetSum = 0 输出：[]
        
        提示：
        
        树中节点总数在范围 [0, 5000] 内
        -1000 'Node': if not head: return cur = head # 1. 复制各节点，并构建拼接链表 while cur: tmp = Node(cur.val) tmp.next = cur.next cur.next = tmp cur = tmp.next # 2. 构建各新节点的 random 指向 cur = head while cur: if cur.random: cur.next.random = cur.random.next cur = cur.next.next # 3. 拆分两链表 cur = res = head.next pre = head while cur.next: pre.next = pre.next.next cur.next = cur.next.next pre = pre.next cur = cur.next pre.next = None # 单独处理原链表尾节点 return res # 返回新链表头节点
        🎃剑指 Offer 36. 二叉搜索树与双向链表
        
        难度中等683
        
        输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
        
        为了让您更好地理解问题，以下面的二叉搜索树为例：
        
        我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
        
        下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点
        
        特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
        
        class Solution: # 中序遍历二叉排序树 = 遍历有序数组 def treeToDoublyList(self, root: 'Node') -> 'Node': if not root: return root self.head = None self.pre = None def dfs(node: Node) -> None: if not node: return dfs(node.left) if self.pre: self.pre.right = node else: # pre前驱为None，说明是第一次见到最小值节点 self.head = node node.left = self.pre self.pre = node dfs(node.right) dfs(root) self.head.left = self.pre self.pre.right = self.head return self.head
        
        🎉剑指 Offer 37. 序列化二叉树
        
        难度困难392
        
        请实现两个函数，分别用来序列化和反序列化二叉树。
        
        你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
        
        **提示：**输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
        
        示例：
        
        输入：root = [1,2,3,null,null,4,5] 输出：[1,2,3,null,null,4,5]
        
        java
        
        public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return ""; Queue q = new LinkedList(); q.add(root); String str = Integer.toString(root.val); while(!q.isEmpty()){ TreeNode node = q.poll(); str += "," + (node.left == null ? "null" : Integer.toString(node.left.val)) + "," + (node.right == null ? "null" : Integer.toString(node.right.val)); if (node.left != null) q.add(node.left); if (node.right != null) q.add(node.right); } System.out.println(str); // input: [1,2,3,null,null,4,5] // serialized result: 1,2,3,null,null,4,5,null,null,null,null return str; } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { if(data.length() == 0) return null; String[] arr = data.split(","); if(arr.length == 0) return null; TreeNode root = new TreeNode(Integer.valueOf(arr[0])); Queue q = new LinkedList(); q.add(root); int idx = 0; while(!q.isEmpty()){ TreeNode node = q.poll(); node.left = arr[++idx].equals("null") ? null : new TreeNode(Integer.valueOf(arr[idx])); node.right = arr[++idx].equals("null") ? null : new TreeNode(Integer.valueOf(arr[idx])); if(node.left != null) q.add(node.left); if(node.right != null) q.add(node.right); } return root; } }
        
        剑指 Offer 38. 字符串的排列
        
        难度中等678
        
        输入一个字符串，打印出该字符串中字符的所有排列。
        
        你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
        
        示例:
        
        输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]
        
        限制：
        
        1 List cs = s.toCharArray(); Arrays.sort(cs); list = new ArrayList res[i] = list.get(i); } return res; } public void dfs(int i){ if(i == cs.length){ list.add(sb.toString()); return; } for(int k = 0; k

微信扫一扫加客服

微信扫一扫加客服

点击启动AI问答