剑指offer

数组与矩阵

数组中重复的数字

找出数组中重复的数字。

在一个长度为 n的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

思路：

  1. 暴力双层for循环，时间复杂度是O(n²)
  2. 原地交换值。题目中说在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内，所以数组的值和索引是零对一，一对一，多对一三种情况，我们要的就是多对一对应的值（即有重复的元素了）。如何让数组元素与所以一一对应（nums[i] = i）呢？排序？空间复杂度O(logn)，原地交换的话空间复杂度是O(1)，时间复杂度是O(n)，因此采用原地交换的方式。
    • nums[i] = i，跳过，往后遍历
    • nums[i] = a，nums[a] = b，如果a != b，就交换两数的值，结果为nums[a] = a，这样索引就与值对应了
    • 如果nums[i] == nums[nums[i]]，说明i位置处和nums[i]数组元素的值相等，找到。

一一对应之后，如果还有和该处索引相等的数组元素值，说明有重复的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findRepeatNumber(int[] nums) {
        int len = nums.length;
        int i = 0;
        while(i < len){
            if(nums[i] == i){
                i++;
                continue;
            }
            if(nums[nums[i]] != nums[i]){
                swap(nums,i,nums[i]);
            }else{
                return nums[i];
            }
        }
        return -1;
    }
    private void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例:

现有矩阵 matrix 如下：

[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。

给定 target = 20，返回 false。

限制：

0 <= n <= 1000
0 <= m <= 1000

思路：

由题意知道，每行每列都是有序的，因此我想到可以从第一行的最后一列开始遍历看是否有这个元素。

初始代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int n = matrix.length;//行
         if(n == 0){
            return false;
        }
        int m = matrix[0].length;//列
        if(m == 0){
            return false;
        }
        for(int i = m - 1; i >= 0; i--){
            if(matrix[0][i] > target){
                continue;
            }
            for(int k = 0; k < n; k++){
                if(matrix[k][i] == target){
                    return true;
                }
            }
        }
        return false;
    }
}

时间复杂度是O(m*n)

优化：还是从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int n = matrix.length;//行
         if(n == 0){
            return false;
        }
        int m = matrix[0].length;//列
        if(m == 0){
            return false;
        }
        int row = 0;
        int col = m - 1;
        while(row < n && col >= 0){
            int cur = matrix[row][col];
            if(cur == target){
                return true;
            }else if(cur > target){
                col--;
            }else{
                row++;
            }
        }
        return false;
    }
}

时间复杂度：O(n+m)。访问到的下标的行最多增加 n 次，列最多减少 m 次，因此循环体最多执行 n + m 次。
空间复杂度：O(1)。

替换空格

请实现一个函数，把字符串 s 中的每个空格替换成”%20”。

示例 1：

输入：s = “We are happy.”
输出：”We%20are%20happy.”

思路：要将空格替换成“%20”，需要将字符串一个字符一个字符的看，所以与字符有关系。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public String replaceSpace(String s) {
        int len = s.length();
        //List<Character> array = new ArrayList<>();
        char[] array = new char[len * 3];
        int size = 0;
        for(int i = 0; i < len; i++){
            char c = s.charAt(i);
            if(c == ' '){
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            }else{
                array[size++] = c;
            }
        }
        String str = new String(array,0,size);
        return str;
    }
}

String str = new String(array,0,size);

String(char[] value, int offset, int count) 分配一个新的 String，它包含取自字符数组参数一个子数组的字符。

K神写的一个方法，直接将字符存到StringBuffer对象中，代码更加简洁

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String replaceSpace(String s) {
        StringBuffer str = new StringBuffer();
        for(Character c : s.toCharArray()){
            if(c == ' '){
                str.append("%20");
            }else{
                str.append(c);
            }
        }
        return str.toString();
    }
}

public char[] toCharArray(): 把字符串转换为字符数组。

顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 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]

思路：按层模拟，每次都是以从左往右、从上往下、从右往左、从下往上的顺序来遍历的，只需要判断边界是否越界。设未遍历矩阵的顶为t（top），底为b（bottom）、左为l（left）、右为r（right）

从左往右，l -> r，矩阵上方减少一层，t++

从上到下，t -> b，矩阵右方减少一列，r–

从右向左，r -> l，矩阵下方减少一层，b–

从下到上，b -> t，矩阵左方减少一层，l++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return new int[0];
        }
        int rows = matrix.length;
        int columns = matrix[0].length;
        int[] res = new int[rows*columns];
        int l = 0;
        int r = columns - 1;
        int t = 0;
        int b =  rows - 1;
        int size = 0;
        while(true){
            for(int i = l; i <= r; i++){
                res[size++] = matrix[t][i];
            }
            if(++t > b) break;
            for(int i = t; i <= b; i++){
                res[size++] = matrix[i][r];
            }
            if(l > --r) break;
            for(int i = r; i >= l; i--){
                res[size++] = matrix[b][i];
            }
            if(t > --b) break;
            for(int i = b; i >= t; i--){
                res[size++] = matrix[i][l];
            }
            if(++l > r) break;
        }
        return res;
    }
}

时间复杂度：O(m*n)，矩阵m行n列，需要把矩阵遍历完

空间复杂度：O(1)，不考虑返回时创建的res

第一次只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = “abaccdeff”
输出：’b’

示例 2:

输入：s = “”
输出：’ ‘

思路：

1.一般计数就想起来哈希表，因此利用哈希表存放字符以及它出现的次数。

2.由于一个字符出现多于一次就不符合要求了，因此 Map 结构的 Value 使用 Boolean 类型是一个更好的选择，而且布尔类型比较节约空间。

3.只要得到第一次出现一次的字符，因此可以采用LinkedHashMap(有序)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public char firstUniqChar(String s) {
        Map<Character,Boolean> map = new LinkedHashMap<>();
        for(char c : s.toCharArray()){
            if(!map.containsKey(c)){
                map.put(c,true);
            }else{
                map.put(c,false);
            }
        }
        for(char c : map.keySet()){
            if(map.get(c)){
                return c;
            }
        }
        return ' ';
    }
}

利用数组，巧妙利用数组下标

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public char firstUniqChar(String s) {
        int[] cc = new int[26];
        char[] chars = s.toCharArray();
        for(char c : chars){
            cc[c-'a']++;
        }
        for(char c : chars){
            if(cc[c-'a'] == 1){
                return c;
            }
        }
        return ' ';
    }
}

时间复杂度 O(N) ： N 为字符串 s 的长度；需遍历 s 两轮，使用 O(N) ；HashMap 查找操作的复杂度为 O(1)；
空间复杂度 O(1) ： 由于题目指出 s 只包含小写字母，因此最多有 26 个不同字符，存储需占用 O(26) = O(1)O(26)=O(1) 的额外空间。

栈和队列

用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

思路：一个栈用于add，一个栈用于delete，队列是先进先出，所以首先出去的是队首，可以利用一个栈弹出元素，然后添加到另一个栈中，在这个栈中栈顶就是队首元素了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class CQueue {
    
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    
    public CQueue() {
        //jdk官方推荐的java栈实现，用Stack实现的话执行用时很长
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.isEmpty() ? -1 : stack2.pop();
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 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(n)，还影响了栈的状态，因为只是想看一下栈的最小元素是哪个。所以利用辅助栈，即定义两个栈，一个栈用于正常栈操作，另一个栈用于存放它遇到的最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MinStack {

    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
        if(stack2.isEmpty() || x <= stack2.peek()){
            stack2.push(x);
        }
    }
    
    public void pop() {
        if(!stack1.isEmpty() && (stack1.pop()).equals(stack2.peek())){
            stack2.pop();
        }
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {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 之前弹出。

思路：采用模拟入栈的方式，借用一个辅助栈 stack ，模拟 压入 / 弹出操作的排列。根据是否模拟成功，即可得到结果。即将数组元素入栈，每次都看栈顶元素是否与popped数组元素相等，如果相等说明这个元素现在需要出栈，就将其出栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        /*if(pushed.length != popped.length){
            return false;
        }*/
        //不知道为什么，这一句比Stack<Integer> stack = new Stack<>();快多了
        Deque<Integer> stack = new ArrayDeque();
        int j = 0;
        for(int num : pushed){
            stack.push(num);
            while(!stack.isEmpty() && stack.peek() == popped[j]){
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

最好使用 LinkedList 实现链表、队列等数据结构

堆

最小的K个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

示例 2：

输入：arr = [0,1,2,1], k = 1
输出：[0]

思路:

大根堆: 想象成二叉树的形状，在每个由三个节点组成的二叉树中，根节点比左右节点都大。

最后一个非叶子节点的下标是k*2-1（k是节点总数，也就是数组长度）。数组元素顺序是按照二叉树的层序遍历排列的。

可以利用大根堆，每次遍历都将小于堆顶的数放进去，最后这个堆中就是数组中最小的数了。不能用小根堆，如果用小根堆（堆顶是最小值），当遍历的这个数比堆顶大的时候，不确定这个数是不是较小的，只能说是比最小值大的数。

java中的优先队列默认是小根堆，使用lamda表达式可以变成大根堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if(arr.length < k || k == 0){
            return new int[0];
        }
        PriorityQueue<Integer> pq = new PriorityQueue<>((v1,v2) -> v2 - v1);//大根堆
        for(int num : arr){
            pq.add(num);
            if(pq.size() > k){
                pq.poll();//移除队首元素
            }
        }
        int[] res = new int[k];
        int i = 0;
        for(int num : pq){//堆的存储方式是数组，一般看成完全二叉树
            res[i] = num;
            i++;
        }
        return res;
    }
}

未完待续…..end….

双指针

和为s的两个数

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

思路：设置双向指针(对撞双指针)，一个从左往右，同时另一个从右往左，逼近target

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        if(len == 1) return new int[0];
        int i = 0;
        int j = len - 1;
        while(i < len && j > i){
            int sum = nums[i] + nums[j];
            if(sum == target){
                 return new int[]{nums[i],nums[j]};
            }
            if(sum < target){
                i++;
            }
            if(sum > target){
                j--;
            }
        }
        return new int[0];
    }
}

和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]

示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

思路: 滑动窗口。一般遇到求连续序列的和的时候，可以往这方面想，因为滑动窗口就是要保持一个固定的target窗口大小，在数组的元素中滑动。窗口的值大于target窗口，就缩小窗口大小，小了就增大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[][] findContinuousSequence(int target) {
        List<int[]> list = new ArrayList<>();
        int i = 1; 
        int j = 2;
        int s = 3;
        while(i < j){
            if(s == target){
                int[] arr = new int[j - i + 1];
                for(int k = i; k <= j; k++){
                    arr[k - i] = k;
                }
                list.add(arr);
            }
            if(s >= target){
                s -= i;
                i++;
            }else{
                j++;
                s += j;
            }
        }
        return list.toArray(new int[list.size()][]);
    }
}

return list.toArray(new int[list.size()] [ ]);

也可以写成return list.toArray(new int[0] [ ]); 原因：

1、数组空间等于0时，将会动态的创建和集合size相同空间大小的数组，性能是最好的。
2、数组空间大于0但是小于size时，会重新创建大小等于集合size的数组，此时会增加GC的负担。
3、数组空间等于集合的size时，在普通情况下是没问题的，但是在高并发情况下，数组创建完成后，集合的size变大，此时影响跟第二条相同。
4、数组空间大于集合的size时，一方面会造成空间浪费，另一方面会在使用数组时产生空指针的异常。因为多出来的空间会存入null

———–参考：https://juejin.cn/post/6844904145753735176

翻转单词顺序

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

注意：题目中提供的字符串s可能只有空格。

示例 1：

输入: “the sky is blue”
输出: “blue is sky the”

示例 2：

输入: “ hello world! “
输出: “world! hello”
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: “a good example”
输出: “example good a”
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路：先将首尾的空格字符去掉，然后在这个范围里再遍历（倒着遍历就可以得到顺序相反的字符串了）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public String reverseWords(String s) {
        char[] chars = s.toCharArray();
        if(chars.length == 0) return "";
        int left = 0;
        int right = chars.length - 1;
        while(chars[left] == ' '){
            left++;
            if(left >= chars.length){
                return "";
            }
        }
        while(chars[right] == ' '){
            right--;
        }
        int i = right;
        StringBuffer sb = new StringBuffer();
        while(i >= left){
            while(i >= left && chars[i] != ' '){
                i--;
            }
            for(int k = i+1; k <= right; k++){
                sb.append(chars[k]);
            }
            while(i >= left && chars[i] == ' '){
                i--;
            }
            if(i != left - 1){
                sb.append(' ');
            }
            
            right = i;
        }
        return sb.toString();
    }
}

将字符串转换成字符数组后，再进行操作的执行时间比直接用s.charAt()快

也可以用双端队列，顺序遍历，将每个单词头插到队列中

或者api选手

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public String reverseWords(String s) {
        s = s.trim(); // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while(i >= 0) {
            while(i >= 0 && s.charAt(i) != ' ') i--; // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while(i >= 0 && s.charAt(i) == ' ') i--; // 跳过单词间空格
            j = i; // j 指向下个单词的尾字符
        }
        return res.toString().trim(); // 转化为字符串并返回
    }
}

左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。

示例 1：

输入: s = “abcdefg”, k = 2
输出: “cdefgab”

示例 2：

输入: s = “lrloseumgh”, k = 6
输出: “umghlrlose”

1
2
3
4
5
6
class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuffer sb = new StringBuffer();
        char[] chars = s.toCharArray();
        for(int i = n; i < s.length(); i++){
            sb.append(chars[i]);
        }
        for(int i = 0; i < n; i++){
            sb.append(chars[i]);
        }
        return sb.toString();
    }
}

链表

从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2]
输出：[2,3,1]

思路：

方法一：利用栈的后进先出特性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        //栈最好用这个实现，java不推荐用Stack实现
        LinkedList<Integer> stack = new LinkedList<>();
        ListNode node = head;
        while(node != null){
            stack.push(node.val);
            node = node.next;
        }
        int[] n = new int[stack.size()];
        int i = 0;
        while(!stack.isEmpty()){
            n[i] = stack.pop();
            i++;
        }
        return n;
    }
}

方法二：递归回溯。因为回溯相当与倒序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    List<Integer> array = new ArrayList<>();
    public int[] reversePrint(ListNode head) {
        huisu(head);
        int[] n = new int[array.size()];
        for(int i = 0; i < array.size(); i++){
            n[i] = array.get(i);
        }
        return n;
    }
    private void huisu(ListNode head){
        if(head == null){
            return;
        }
        huisu(head.next);
        array.add(head.val);
    }
}

在O(1)时间内删除链表节点

给定单向链表的头指针和一个节点指针，定义一个函数在O（1）时间内删除该节点。

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

说明：

  • 题目保证链表中节点的值互不相同

思路：不能挨个遍历，不然时间复杂度是O(N)。

两种情况：

**1.**删除的节点不是尾结点，直接采取要删除节点后面的结点的值覆盖要删除节点的值，然后实际删除的是后继结点的后继结点，时间复杂度为O(N)

**2.**要删除的结点是尾结点，它没有后继结点，因此需要挨个遍历了，时间复杂度是O(N)

平均时间复杂度：进行N次，需要操作结点N-1+N=2N-1次，所以平均时间复杂复杂度为O(2N-1/N)=O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode deleteNode(ListNode head, ListNode tobeDelete) {
    if (head == null || tobeDelete == null)
        return null;
    if (tobeDelete.next != null) {
        // 要删除的节点不是尾节点
        ListNode next = tobeDelete.next;
        tobeDelete.val = next.val;
        tobeDelete.next = next.next;
    } else {
        if (head == tobeDelete)
             // 只有一个节点
            head = null;
        else {
            ListNode cur = head;
            while (cur.next != tobeDelete)
                cur = cur.next;
            cur.next = null;
        }
    }
    return head;
}

删除排序链表中的重复元素II

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表

示例1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例2：

输入：head = [1,1,1,2,3]
输出：[2,3]

思路：因为头结点也可能被删除，所以设置一个虚拟头结点，可以动态地指向链表的最终的头结点。需要用变量保存重复的值，然后依次遍历，删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode dummyNode = new ListNode(-1,head);
        ListNode cur = dummyNode;
        while(cur.next != null && cur.next.next!= null){
            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;
                }
            }else{
                cur = cur.next;
            }
        }
        return dummyNode.next;
    }
}

需要说明的一点是 ListNode cur = dummyNode; 因此现在cur就是dummyNode，cur找第一个没重复的元素就是在改变dummy的next指针，后面跳走了，dummy就没变了，只是dummy->next->next在变

递归：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode cur = head;
        ListNode next = cur.next;
        if(cur.val == next.val){
            //头结点需要删除
            int x = next.val;
            while(next != null && next.val == x){
                next = next.next;
            }
            return deleteDuplicates(next);
        }else{
            //不删除头结点
            cur.next = deleteDuplicates(next);
            return head;
        }
        
    }
}

链表中倒数第K个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.

返回链表 4->5.

思路：

方法一：利用栈的后进先出特性，倒序弹出倒数第K个节点

方法二：由于方法一需要创建一个栈，导致空间复杂度不为O(1)。所以考虑使用双指针，让一个指针先走k步，即剩下n-k个结点没有走，n是链表的总节点数，然后让两个指针同时移动，当快指针为null时，说明已经走了n-k步，此时慢指针就是倒数第k个节点所在的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if(head == null) return null;
        ListNode node1 = head;
        ListNode node2 = head;
        for(int i = 0; i < k; i++){
            node2 = node2.next;
        }
        while(node2 != null){
            node1 = node1.next;
            node2 = node2.next;
        }
        return node1;
    }
}

链表中环的入口节点

给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

示例 1：

img

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 3：

img

输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

思路：

方法一：双指针法。

设置两个指针，fast一次走两步，slow一次走一步，设环有b个节点，链表一共a+b个节点。因为每次fast指针都比slow指针多走一步，所以如果有环的话，两指针一定会相遇。即fast一定会追上slow。设两个指针分别移动了f s步，则f=2s（每次fast走2步，slow走一步），两者相遇，fast比slow多走n圈，即f=s+nb。因此f=2nb，s=nb。

如果让指针从链表头部一直向前走并统计步数 k ，那么所有 走到链表入口节点时的步数 是：k = a + nb（先走 a 步到入口节点，之后每绕 11 圈环（ b 步）都会再次到入口节点）。

所以让s再走a步，就可以到达环入口结点，如何指示这个a的值？利用节点从head开始移动到环入口正好是a

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(true){
            if(fast == null || fast.next == null){
                return null;
            }
            fast = fast.next.next;
            slow = slow.next;
            if(slow == fast){
                break;
            }
        }
        fast = head;
        while(slow != fast){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}
  • 时间复杂度：O(N)
  • 空间复杂度：O(1)

方法二: 哈希表

有环没环其实就是看是否遍历到重复的节点，因此可以利用Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        Set<ListNode> set = new HashSet<>();
        while(cur != null){
            if(!set.contains(cur)){
                set.add(cur);
            }else{
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
}
  • 时间复杂度：O(N)
  • 空间复杂度：O(N)。没环，链表的所有节点都要放到哈希表中

翻转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

示例1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

思路：

1.迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head;
        ListNode prev = null;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
}

时间复杂度O(n)，空间复杂度O(1)

2.递归

把后面的看做整体，假设已经被翻转，因此现在只需要将头节点翻转

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode reverseList(ListNode head) {
        //递归终止条件
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

递归相当于调用栈，因此空间复杂度为O(n)

合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

0 <= 链表长度 <= 1000

思路：设置一个虚拟头结点，将两个链表的节点经过比较大小后重新链入一个新的链表中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 != null){
            cur.next = l1;
        }else{
            cur.next = l2;
        }
        return dummyNode.next;
    }
}

复杂链表的复制

在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。你需要重新创建节点，复制一个全新的链表，和原链表完全一样！！

示例 1：

img

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

思路：

方法一：利用哈希表，旧链表的每个节点为key,新链表的每个节点为value。通过两次遍历，第一次创建节点并将节点存放到哈希表中，第二次遍历设置新节点的next和random。

为什么要遍历两次呢？因为第一次需要先将有哪些节点创建出来。

Picture1.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        Map<Node,Node> map = new HashMap<>();
        Node cur = head;
        while(cur != null){
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

两个链表的第一个公共节点

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

img

在节点 c1 开始相交。

思路：

1.哈希表。哈希表先存一个链表的所有节点，在顺序遍历另一个链表，如果节点在哈希表中有，那就是交点。缺点是时间复杂度和空间复杂度都是O(N)。

2.双指针。

  • 链表有公共节点（相交）

    设公共节点有c个，对于A链表，第一个公共节点前有a个节点，对于B链表，第一个公共节点前共有b个节点，设两指针headA从A链表头开始遍历 和headB从B链表头开始遍历

    如果a=b，那么两节点同时到达交点

    如果a!=b，那么肯定有一个指针先遍历到链表尾部，此时使该指针遍历另一个链表。最终两指针一定会相交。因为headA指针走了a+c+b个节点，headB指针走了b+c+a个节点

  • 链表没有公共节点（不相交）

    如果a=b，同时到达链表尾部

    如果a!=b，A指针走a+c+b B指针走b+c+a，同时到达null尾结点

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while(A != B){
            A = A == null ? headB : A.next;
            B = B == null ? headA : B.next;
        }
        return A;
    }
}

时间复杂度：O(N)，空间复杂度：O(1)

二叉树

二叉树的镜像

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：

​ 4

​ /
2 7
/ \ / \
1 3 6 9
镜像输出：

​ 4

​ /
7 2
/ \ / \
9 6 3 1

思路：

方法一：借助栈将每层的子树根节点的左右孩子都交换。就是在层序遍历中多加一步。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.addLast(root);
        while(!stack.isEmpty()){
            TreeNode node = stack.removeLast();
            if(node.left != null){
                stack.addLast(node.left);
            }
            if(node.right != null){
                stack.addLast(node.right);
            }
            TreeNode tmp = node.left;
            node.left = node.right;
            node.right = tmp;
        }
        return root;
    }
}

时间复杂度O(N)

空间复杂度O(N)。最差情况下，栈 stack 最多同时存储（N + 1）/2个节点，占用 O(N) 额外空间。

Picture0.png

——引用力扣K神题解

2.递归

1
2
3
4
5
6
7
8
9
10
class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if(root == null) return null;
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

不要试着去理解递归内部的逻辑意义，相信它可以做到。直接用

空间复杂度O(N) 。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，即 O(logN)。而在最坏情况下，树形成链状，空间复杂度为 O(N)。

树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

​ 3

​ / \

4 5
/
1 2
给定的树 B：

4
/
1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

思路：

如果两个树中其中一个为空，就不能有子结构。因为我们默认空树不能有子结构。

现在我们就是要找在A树中有和B树根节点相同的节点，然后在A树中以这个节点为根节点的子树是否与B树结构和值相同，如果不相同，就找另一个与B根节点值相同的节点，继续判断。

1.先在A树中找到与B树根节点值相同的节点P
2、以P节点作为根节点，与B树做比较
B树有的子节点，A树必须有
B树没有的子节点，A树可以有

——引用B站UP主子烁爱学习

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        if(A.val == B.val && isContains(A,B)) return true;
        return isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
    //这个函数的作用就是判断以node1为根节点的树与以node2为根节点的树是否完全相同
    private boolean isContains(TreeNode node1,TreeNode node2){
        if(node1 == null && node2 != null) return false;
        if(node2 == null) return true;
        return node1.val == node2.val && isContains(node1.left,node2.left) && isContains(node1.right,node2.right);
    }
}

对称的二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的

思路：采用递归，整体的看左节点和右节点是否具有相同的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return recur(root.left,root.right);//看左子树和右子树是否是镜像对称的
    }
    private boolean recur(TreeNode left,TreeNode right){
        if(left == null && right == null) return true;
        if(left == null || right == null || left.val != right.val) return false;
        //看左子树的以左结点为根的子树与右子树以右节点为根的子树是否是对称的
        //看左子树的以右结点为根的子树与右子树以左节点为根的子树是否是对称的
        return recur(left.left,right.right) && recur(left.right,right.left);
    }
}

时间复杂度：O(N) 。需要判断N/2个节点对是否对称

空间复杂度：O(N)。使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。在平均情况下，二叉树的高度与节点个数为对数关系，空间复杂度为 O(logN)。当二叉树退化成链表时，高度是(N+1)/2，空间复杂度是O(N)

从上到下打印二叉树II

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行

思路：

利用队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
         LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        while(!queue.isEmpty()){
            List<Integer> arr = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node = queue.removeFirst();
                arr.add(node.val);
                if(node.left != null){
                    queue.addLast(node.left);
                }
                if(node.right != null){
                    queue.addLast(node.right);
                }
            }
            list.add(arr);
        }
        return list;
    }
}

从上到下打印二叉树III

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

思路：

双端队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if(root == null) return list;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.addLast(root);
        boolean flag = true;//true 从左往右打印，false 从右往左打印
        while(!queue.isEmpty()){
            List<Integer> arr = new ArrayList<>();
            int size = queue.size();
            for(int i = 0; i < size; i++){
                TreeNode node;
                if(flag){//本层是从左往右打印
                    node = queue.removeFirst();
                    arr.add(node.val);
                    if(node.left != null){
                        queue.addLast(node.left);
                    }
                    if(node.right != null){
                        queue.addLast(node.right);
                    }
                }else{//本层是从右往左打印
                    node = queue.removeLast();
                    arr.add(node.val);
                    //因为下一层从左往右打印，因此需要先放右孩子节点，再放左孩子节点，然后从队列头取节点的顺序才正确；
                    if(node.right != null){
                        queue.addFirst(node.right);
                    }
                    if(node.left != null){
                        queue.addFirst(node.left);
                    }
                }
                
            }
            flag = flag ? false : true;
            list.add(arr);
        }
        return list;
    }
}

时间复杂度 O(N) N为二叉树的节点个数，循环

空间复杂度 O(N) 当二叉树为满二叉树时，队列中最多存放（N+1）/2个节点，即最下面一层的节点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            LinkedList<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                if(res.size() % 2 == 0) tmp.addLast(node.val); // 偶数层 
                else tmp.addFirst(node.val); // 奇数层 
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
            }
            res.add(tmp);//List的主要实现包括LinkedList及ArrayList。因此可以直接添加
        }
        return res;
    }
}

K神这个题解直接利用res来判断层数是奇数还是偶数，如果是奇数，顺序插入到链表中，如果是偶数，倒序插入到链表中，这样就不需要利用双端队列了。

使用res.size() % 2 == 0来判断是奇数层（从左往右打印），还是偶数层（从右往左打印）

二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

思路：

方法一：递归+分治

根据定义，二叉搜索树的左子树中的所有节点值都小于根节点的值，右子树中的所有节点都大于根节点的值。根据后序遍历的顺序，输入数组的最后一个元素就是根节点。

在输入数组中找到左子树和右子树的部分，然后判断左子树的元素序列和右子树的元素序列是否符合一个二叉搜索树的后序遍历的顺序，一直递归+分治，递归终止条件是左右边界重合或者左边界超过右边界（不正确的边界），即没有左子树或者右子树了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return verifyPostorder(postorder,0,postorder.length - 1);
    }
    private boolean verifyPostorder(int[] postorder,int start,int end){
        if(start >= end) return true;
        int pointer = start;
        while(postorder[pointer] < postorder[end]){
            pointer++;
        }
        int mid = pointer;
        //pointer此时位于右子树的第一个节点索引处
        while(postorder[pointer] > postorder[end]){
            pointer++;
        }
        return pointer == end && verifyPostorder(postorder,start,mid - 1) && verifyPostorder(postorder,mid,end - 1);
    }
}

pointer == end条件说明这个树符合后序遍历，是一个正确的树

**时间复杂度 O(N^2)**： 每次调用 recur(i,j) 减去一个根节点，因此递归占用 O(N) ；最差情况下（即当树退化为链表），每轮递归都需遍历树所有节点，占用 O(N) 。
空间复杂度 O(N)： 最差情况下（即当树退化为链表），递归深度将达到 N 。

复杂度分析引用力扣K神题解

方法二：单调栈

将数组倒序过来，如果postorder[i] < postorder[i+1]，说明postorder[i+1]是postorder[i]的右子节点，postorder[i]是postorder[i+1]的父节点。因为后序遍历中每个子树中的根节点都是最后遍历的，所以postorder[i+1]一定是postorder[i]的右子树的根节点。

如果postorder[i] > postorder[i+1]，说明postorder[i+1]是前面其中一个节点的左子树的根节点，postorder[i] - postorder[i+1]的绝对值最小，postorder[i]就是postorder[i+1]的父节点。

由于他们具有单调递增和单调递减的性质，所以可以采用单调栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean verifyPostorder(int[] postorder) {
        LinkedList<Integer> stack = new LinkedList<>();
        int parent = Integer.MAX_VALUE;
        for(int i = postorder.length - 1; i >=0; i--){
            //遍历的节点postorder[i]一定位于当前parent节点的左子树中
            //所以一定要postorder[i] > parent
            if(postorder[i] > parent) return false;
            while(!stack.isEmpty()&&stack.peekLast() > postorder[i]){
                parent = stack.removeLast();
            }
            stack.addLast(postorder[i]);
        }
        return true;
    }
}

时间复杂度o(n) 空间复杂度o(n)

二叉树中和为某一值的路径

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

叶子节点 是指没有子节点的节点。

思路：

先序遍历+回溯

因为list是引用传递，全过程只有一个，所以当最后对list进行的回溯操作会影响res中已经添加的list对象，所以res在添加的时候需要重新拷贝一份list。

而target不需要回溯，因为它是值传递，每次递归都会重新赋值一个新的target。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int target) {
        List<Integer> list = new ArrayList<>();
        preOrder(root,target,list);
        return res;
    }
    private void preOrder(TreeNode node,int target,List<Integer> list){
        if(node == null) return;
        list.add(node.val);
        target -= node.val;
        if(target == 0&&node.right == null && node.left == null){
              res.add(new ArrayList<>(list));
        }
        preOrder(node.left,target,list);
        preOrder(node.right,target,list);
        list.remove(list.size() - 1);// 向上回溯前，需要将当前节点从路径 path 中删除，
    }
}

二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

就是本来两个节点之间只有一个指针，现在需要加一个反向的指针，就构成了双向指针。

思路：

循环链表需要头节点和尾节点也有双向指针。

因为题目中要求转换成排序的循环双向链表，所以是在中序遍历的过程中，多添加一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    private Node head;
    private Node pre;
    public Node treeToDoublyList(Node root) {
        if(root == null) return null;
        inOrder(root);
        head.left = pre;
        pre.right = head;
        return head;
    }
    private void inOrder(Node cur){
        if(cur == null) return;
        inOrder(cur.left);
        cur.left = pre;
        if(pre == null){
            head = cur;
        }else{
            pre.right = cur;
        }
        pre = cur;
        inOrder(cur.right);
    }
}

二叉搜索树的第k大节点

给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

思路：

中序遍历的倒序，在倒序中序遍历的过程中寻找第k大的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    int k;
    int res;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        inOrder(root);
        return res;
    }
    private void inOrder(TreeNode node){
        if(node == null) return;
        inOrder(node.right);
        if(k == 0) return;
        k--;//遍历一个节点就将k减1，当减到0，说明它就是第k大的节点
        if(k == 0) res = node.val;
        inOrder(node.left);
    }
}

时间复杂度：O(N) //这个不太明白

空间复杂度：O(N)：使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度。当二叉树退化成链表时，深度是N 。

二叉树的深度

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

思路：

方法一：BFS

最大深度就是左子树和右子树他们的最大深度加上根节点的高度1

1
2
3
4
5
6
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1;
    }
}

时间复杂度：O(N)：n为树的节点个数，需要遍历所有节点才能算出树的深度

空间复杂度：O(N)：递归栈的深度取决于树的深度，树的深度最大为N（退化成链表）

方法二：

层序遍历+队列

每遍历一层，depth+1，所以我们要控制每次循环就遍历一层。可以使用tmp临时存储每层中的节点，每次都将每层全部赋值给队列，然后一次循环，全部遍历，再开启新的一层

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        int depth = 0;
        while(!deque.isEmpty()){
            LinkedList<TreeNode> tmp = new LinkedList<>();
            for(TreeNode node : deque){
                if(node.left != null){
                    tmp.addLast(node.left);
                }
                if(node.right != null){
                    tmp.addLast(node.right);
                }
            }
            deque = tmp;
            depth++;
        }
        return depth;
    }
}

时间复杂度：O(N)：n为树的节点个数，需要遍历所有节点才能算出树的深度

空间复杂度：O(N)：最差情况下（当树为满二叉树时），队列 queue 同时存储 (N+1)/2 个节点

平衡二叉树

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

思路：

方法一：深度优先遍历。先序遍历，从顶至底

一棵二叉树是平衡二叉树的条件：

  1. 它的左子树和右子树高度相差1
  2. 左子树和右子树本身也是平衡二叉树
1
2
3
4
5
6
7
8
9
10
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        return Math.abs(depth(root.left)-depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }
    private int depth(TreeNode node){
        if(node == null) return 0;
        return Math.max(depth(node.left),depth(node.right)) + 1;
    }
}

时间复杂度：O(nlogn) 最坏的情况下(满二叉树)，需要遍历所有节点判断以这个节点为根节点的子树是否是平衡二叉树，满二叉树的高度是O(logn)。各层执行 depth(root) 的时间复杂度为 O(N) （每层开始，最多遍历 N个节点，最少遍历 （N+1）/2个节点）。–（不太理解）

—-引用力扣K神

空间复杂度：O(N)。最差情况下（树退化为链表时），系统递归需要使用 O(N) 的栈空间。

方法二：

自底向下的后序遍历

一直获取root的最左边的节点，以及最右边的节点，逐层往上依次判断节点是否是高度小于等于1，比如对于root的左子树中的其中一个节点，这个节点是某一个节点的左结点，它不是平衡的，那么就会返回-1，这个节点的父节点的left就会返回-1，然后一直往上遍历，每到if判断中就会返回-1，最终-1返回到root，结束，而root 的右子树就不需要再遍历了，节省了很多时间

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isBalanced(TreeNode root) {
        return heigth(root) != -1;
    }
    private int heigth(TreeNode root){
        if(root == null) return 0;
        int left = heigth(root.left);
        if(left == -1) return -1;
        int right = heigth(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) <= 1 ? Math.max(left,right) + 1 : -1;
    }
}

时间复杂度 o(n) 最差需要遍历所有节点

空间复杂度 o(n)

二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

思路：

方法一：一次遍历

两个节点只有三种情况：

  1. 两个节点都位于根节点的左子树中
  2. 两个节点都位于根节点的右子树中
  3. 一个节点位于根节点的左子树，一个节点位于根节点的右子树（这种情况下根节点就是他们的最近公共祖先节点）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root != null){
            int rootValue = root.val;
            int pValue = p.val;
            int qValue = q.val;
            if(rootValue > pValue && rootValue > qValue){
                //两节点都位于二叉树的左子树
                root = root.left;
            }else if(rootValue < pValue && rootValue < qValue){
                //两节点都位于二叉树的右子树
                root = root.right;
            }else{
                //一个位于左子树，一个位于右子树，说明root此时就是最近的公共节点
                break;
            }
        }
        return root;
    }
}

也可以优化，始终令p.val>q.val

——未完待续

DateStructure
#数据结构 #剑指offer
剑指offer
https://vickkkyz.fun/2022/03/24/计算机/LeetCoode/剑指offer/
作者
Vickkkyz
发布于
2022年3月24日
许可协议