Leetcode刷题记录

前言

在此篇开始前已完成代码随想录一刷，对于算法题算是初窥门径，但是一刷的周期很长，有很多东西已经记不清了，而且有很多对我于个人来说比较妙且有用的语法表达（基于Java）没有记录。故开此篇，总体上依照代码随想录的顺序开启二刷，并记录下遇到的难点和一些感想。

由衷感谢“卡哥”的开源精神！

代码随想录：https://programmercarl.com/

在每道题的标题后面会有一些符号：

• 无任何符号：没有思路 or 没有通过全部样例 or 解题过程中参考了一些题解思路
• ✔：Acess！
• ❗：在编写代码的过程中遇到一些语法上的问题，或者是一些巧妙的解题思路，需要留意

---

Leetcode

数组

【704】二分查找✔

题目链接：704. 二分查找 - 力扣（LeetCode）

题解：

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        // int mid = (right - left) / 2 + left;  //防止溢出的表达
        int mid = (left + right) / 2;  //也可以

        while(left <= right) {  //注意区间的表达
            mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                left = mid + 1;  //注意区间的表达
            }
            if(nums[mid] > target) {
                right = mid - 1;  //注意区间的表达
            }
        }

        return -1;
    }
}

1. int mid = (right - left) / 2 + left;是一种防溢出的表达。
2. 注意区间的表达。

【35】搜索插入位置✔

题目链接：35. 搜索插入位置 - 力扣（LeetCode）

题解：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid = (left + right) / 2;

        while(left <= right) {
            mid = (left + right) / 2;
            if(nums[mid] == target) {
                return mid;
            }
            if(nums[mid] < target) {
                left = mid + 1;
            }
            if(nums[mid] > target) {
                right = mid - 1;
            }
        }
        return left;  //注意返回值
    }
}

1. 使用二分法。
2. 注意返回值。

【34】在排序数组中查找元素的第一个和最后一个位置

题目链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

题解：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = {-1, -1};
        if(nums.length == 0) {
            return result;
        }

        // 找左边界
        int left1 = 0;
        int right1 = nums.length - 1;
        int mid1 = (left1 + right1) / 2;
        int left_board = -1;
        while(left1 <= right1) {
            mid1 = (left1 + right1) / 2;
            if(nums[mid1] == target) {
                left_board = mid1;  //记录结果
                right1 = mid1 - 1;  //关键，使搜索区间更靠近左侧
            }
            if(nums[mid1] > target) {
                right1 = mid1 - 1;
            }
            if(nums[mid1] < target) {
                left1 = mid1 + 1;
            }
        }

        // 找右边界
        int left2 = 0;
        int right2 = nums.length - 1;
        int mid2 = (left2 + right2) / 2;
        int right_board = -1;
        while(left2 <= right2) {
            mid2 = (left2 + right2) / 2;
            if(nums[mid2] == target) {
                right_board = mid2;  //记录结果
                left2 = mid2 + 1;  //关键，使搜索区间更靠近右侧
            }
            if(nums[mid2] > target) {
                right2 = mid2 - 1;
            }
            if(nums[mid2] < target) {
                left2 = mid2 + 1;
            }
        }

        result[0] = left_board;
        result[1] = right_board;

        return result;
    }
}

思路：直接利用二分法分别找到左右边界。

与基础二分法题目不同的是，如果nums[mid] == target，则需要根据查找的左、右目标边界，相对应地移动当前的右、左边界。目的是使当前的搜索区间更靠近目标方向。

【69】x的平方根

题目链接：69. x 的平方根 - 力扣（LeetCode）

题解：

class Solution {
    public int mySqrt(int x) {
        int left = 0;
        int right = x;
        int mid = (right + left) / 2;

        while(left <= right) {
            mid = (right + left) / 2;
            if((long) mid * mid == x) {
                return mid;
            }
            if((long) mid * mid < x) {
                left = mid + 1;
            }
            if((long) mid * mid > x) {
                right = mid - 1;
            }
        }
        return left - 1;
    }
}

由于返回的值只要求整数部分，可以使用二分法查找。

注意：在计算判断语句中(long) mid * mid不可以写为(long) (mid * mid)，后者如果当(mid * mid)计算结果溢出，再转为long类型没有意义，依旧会报错。

【367】有效的完全平方数✔

题目链接：367. 有效的完全平方数 - 力扣（LeetCode）

题解：

class Solution {
    public boolean isPerfectSquare(int num) {
        int left = 0;
        int right = num;
        int mid = (left + right) / 2;

        while(left <= right) {
            mid = (left + right) / 2;
            if((long) mid * mid == num) {
                return true;
            }
            if((long) mid * mid < num) {
                left = mid + 1;
            }
            if((long) mid * mid > num) {
                right = mid - 1;
            }
        }
        return false;
    }
}

正常使用二分法解决

【27】移除元素✔

题目链接：27. 移除元素 - 力扣（LeetCode）

题解：

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow = 0;  //定义一个慢指针
        for(int fast = 0; fast < nums.length; fast++) {  //定义一个快指针，并利用for循环控制
            if(nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
        }
        return slow;
    }
}

双指针的一种思路：将快指针定义在for循环条件处，并利用for循环控制快指针移动，覆盖前面的目标值。

【26】删除有序数组中的重复项✔

题目链接：26. 删除有序数组中的重复项 - 力扣（LeetCode）

题解：

class Solution {
    public int removeDuplicates(int[] nums) {
        int slow = 0;
        for(int fast = 0; fast < nums.length; fast++) {
            if(nums[fast] > nums[slow]) {
                slow++;  // 先移动指针
                nums[slow] = nums[fast];  // 再进行替换
            }
        }
        return slow + 1;  // 注意返回值
    }
}

双指针解法，这里注意要先移动指针再替换。

【283】移动零✔

题目链接：283. 移动零 - 力扣（LeetCode）

题解：

class Solution {
    public void moveZeroes(int[] nums) {
        int slow = 0;
        // 先将slow指针移动到第一个0处
        while(slow < nums.length && nums[slow] != 0) {
            slow++;
        }
        // fast指针初始化和slow一致
        for(int fast = slow; fast < nums.length; fast++) {
            if(nums[fast] != 0) {
                nums[slow] = nums[fast];
                nums[fast] = 0;  // 相当于交换
                slow++;
            }
        }
    }
}

双指针思路：先将slow指针移动到第一个0处，注意不要让slow指针超出数组范围，再初始化fast指针，初始化和slow指针一致。

【844】比较含退格的字符串✔

题目链接：844. 比较含退格的字符串 - 力扣（LeetCode）

题解：

class Solution {
    public boolean backspaceCompare(String s, String t) {
        char[] s_list = s.toCharArray();
        char[] t_list = t.toCharArray();
        Stack<Character> s_stack = new Stack<>();
        Stack<Character> t_stack = new Stack<>();

        // 处理s
        for(int i = 0; i < s_list.length; i++) {
            // 如果不是'#'，则字母入栈
            if(s_list[i] != '#') {
                s_stack.push(s_list[i]);
            }
            // 如果是'#'，则先判断栈是否为空：如果栈为空，则跳过，否则弹出字母
            else if(s_list[i] == '#') {
                if(s_stack.isEmpty()) {
                    continue;
                } else {
                    s_stack.pop();
                }
            }
        }
        // 处理t
        for(int i = 0; i < t_list.length; i++) {
            // 如果不是'#'，则字母入栈
            if(t_list[i] != '#') {
                t_stack.push(t_list[i]);
            }
            // 如果是'#'，则先判断栈是否为空：如果栈为空，则跳过，否则弹出字母
            else if(t_list[i] == '#') {
                if(t_stack.isEmpty()) {
                    continue;
                } else {
                    t_stack.pop();
                }
            }
        }

        // 如果两个栈长度不一致，直接返回false
        if(s_stack.size() != t_stack.size()) {
            return false;
        }
        // 逐个弹出元素判断
        while(!s_stack.isEmpty()) {
            if(s_stack.pop() != t_stack.pop()) {
                return false;
            }
        }

        return true;
    }
}

很容易联想到栈，利用栈解决。

【977】有序数组的平方✔

题目链接：977. 有序数组的平方 - 力扣（LeetCode）

题解：

class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        
        //左右指针从数组两边往中间靠，result数组从后往前添加
        for(int i = result.length - 1; i >= 0; i--) {
            if(Math.abs(nums[left]) > Math.abs(nums[right])) {
                result[i] = nums[left] * nums[left];
                left++;
            } else {
                result[i] = nums[right] * nums[right];
                right--;
            }
        }
        return result;
    }
}

双指针解法：左右指针从数组两边往中间靠，result数组从后往前添加，依次添加绝对值最大的数字的平方。

【209】长度最小的子数组✔

题目链接：209. 长度最小的子数组 - 力扣（LeetCode）

题解：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;  // 定义左边界
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {  // 定义右边界
            sum += nums[right];  //for循环每一轮都向右边扩展
            // 一旦sum满足条件，就利用left左边界缩小范围
            while (sum >= target) {
                result = Math.min(result, right - left + 1);  
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

利用双指针构成滑动区间解决。关键思路：for循环条件内定义右边界，每轮循环扩展右边界，一旦sum满足条件，就利用while循环缩小左边界。

【904】水果成篮

题目链接：904. 水果成篮 - 力扣（LeetCode）

题解：

class Solution {
    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> map = new HashMap<>();
        int left = 0;
        int result = 0;

        // 创建right，利用for循环不断遍历水果
        for(int right = 0; right < fruits.length; right++) {
            // 如果篮子有当前水果，直接把当前水果放入到对应的篮子里
            if(map.containsKey(fruits[right])) {
                map.put(fruits[right], map.get(fruits[right]) + 1);
                result = Math.max(result, right - left + 1);  // 计算最大值
            } 
            // 如果篮子没有当前水果
            else {
                // 如果篮子数量小于2，则直接创建一个新篮子，把当前水果放到该篮子中
                if(map.size() < 2) {
                    map.put(fruits[right], 1);
                    result = Math.max(result, right - left + 1);  // 计算最大值
                } 
                // 如果篮子数量大于2
                else {
                    map.put(fruits[right], 1);  // 先创建一个新篮子，然后把当前水果放到该篮子中
                    // 利用while循环删除包含fruits[left]的篮子（关键）
                    // 必须要逐步移动left，因为这个过程可能包含另外一种水果，也需要把该水果的数量减一
                    while(map.size() > 2) {
                        map.put(fruits[left], map.get(fruits[left]) - 1);
                        if(map.get(fruits[left]) == 0) {
                            map.remove(fruits[left]);
                        }
                        left++;
                    }
                }
            }
        }
        return result;
    }
}

利用滑动窗口的思想解题，用map记录水果种类（篮子）。

做题踩坑点：一开始想到了解题思路，但是在删除包含fruits[left]的篮子过程中没有逐步移动left，而是直接清空map中的fruits[left]，再重定位left。这样可能导致区间[left, right-1]中包含另一种水果的数量没有及时减去，导致最终结果偏大。

【76】最小覆盖子串✔❗

题目链接：76. 最小覆盖子串 - 力扣（LeetCode）

题解：

class Solution {
    public String minWindow(String s, String t) {
        char[] s_list = s.toCharArray();
        char[] t_list = t.toCharArray();
        Map<Character, Integer> s_map = new HashMap<>();
        Map<Character, Integer> t_map = new HashMap<>();

        // 初始化t_map
        for(int i = 0; i < t_list.length; i++) {
            t_map.put(t_list[i], t_map.getOrDefault(t_list[i], 0) + 1);
        }

        int left = 0;  //定义左指针
        StringBuilder sb = new StringBuilder();
        String result = s + t;  // 初始化result，一定要大于字符串s的长度（初始值无所谓）

        // 在for循环中定义右指针
        for(int right = 0; right < s_list.length; right++) {
            // 每轮循环不停地移动右指针，sb跟随着添加字符
            s_map.put(s_list[right], s_map.getOrDefault(s_list[right], 0) + 1);
            sb.append(s_list[right]);
            // 一旦符合题目中的条件，就移动左指针，缩小区间
            while(judge(s_map, t_map)) {
                s_map.put(s_list[left], s_map.get(s_list[left]) - 1);
                left++;
                result = result.length() < sb.toString().length() ? result : sb.toString();  // 先收集结果
                sb.deleteCharAt(0);  // 再缩减sb
            }
        }

        return result = result.equals(s + t) ? "" : result;
    }

    // 定义judge函数用于判断是否满足题目条件：s_map中是否全部包含t_map的“键”，并且大于等于“值”
    public Boolean judge(Map<Character, Integer> s_map, Map<Character, Integer> t_map) {
        for(Map.Entry<Character, Integer> entry : t_map.entrySet()) {
            if(!s_map.containsKey(entry.getKey())) {
                return false;
            }
            else if(s_map.get(entry.getKey()) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }
}

利用滑动区间解决问题，复杂的地方在于对字符串操作。

一些语法需要注意❗

• Map集合的创建方式：

  Map<Character, Integer> s_map = new HashMap<>();

• Map集合设定默认值的添加方法.getOrDefault(Key, Value)：

  t_map.put(t_list[i], t_map.getOrDefault(t_list[i], 0) + 1);

• StringBuilder的添加和删除方法：

  sb.append(s_list[right]);  //添加
  sb.deleteCharAt(0);  //删除指定位置的元素

• Map集合的forEach遍历方式：

  for(Map.Entry<Character, Integer> entry : t_map.entrySet()) {
      entry.getKey();
      entry.getValue();
  }

【59】螺旋矩阵Ⅱ✔

题目链接：59. 螺旋矩阵 II - 力扣（LeetCode）

题解：

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];
        int number = 1;  // 定义填入的数字
        int offset = 1;  // 定义偏移量
        int x = 0, y = 0;  // 定义坐标
        int round = n / 2;  // 循环的轮次

        // 每次while循环就是一轮
        while(round > 0) {
            // 左上→右上
            for(; y < n - offset; y++) {
                matrix[x][y] = number;
                number++;
            }
            // 右上→右下
            for(; x < n - offset; x++) {
                matrix[x][y] = number;
                number++;
            }
            // 右下→左下
            for(; y > offset - 1; y--) {
                matrix[x][y] = number;
                number++;
            }
            // 左下→左上
            for(; x > offset - 1; x--) {
                matrix[x][y] = number;
                number++;
            }
            x++;
            y++;
            offset++;
            round--;
        }
        // 如果n为奇数，则最中心的位置单独填入数字
        if(n % 2 == 1) {
            int index = n / 2;
            matrix[index][index] = n * n;
        }

        return matrix;
    }
}

解题思路就是模拟转圈填写数字，利用offset控制每一圈的起止位置。

【54】螺旋矩阵✔

题目链接：54. 螺旋矩阵 - 力扣（LeetCode）

题解：

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int x = 0, y = 0;
        int offset = 1;  // 定义偏移量
        int x_length = matrix.length;  // 定义x_length
        int y_length = matrix[0].length;  // 定义y_length
        int round = Math.min(x_length, y_length) / 2;  // 循环的轮次

        // 每次while循环就是一轮
        while(round > 0) {
            // 左上→右上
            for(; y < y_length - offset; y++) {
                result.add(matrix[x][y]);
            }
            // 右上→右下
            for(; x < x_length - offset; x++) {
                result.add(matrix[x][y]);
            }
            // 右下→左下
            for(; y > offset - 1; y--) {
                result.add(matrix[x][y]);
            }
            // 左下→左上
            for(; x > offset - 1; x--) {
                result.add(matrix[x][y]);
            }
            x++;
            y++;
            offset++;
            round--;
        }

        // 如果x_length和y_length中的最小值为偶数，那么上述循环一定可以全部遍历
        // 如果x_length和y_length中的最小值为奇数，那么就需要分类遍历剩余的数字
        if(Math.min(x_length, y_length) % 2 == 1) {
            // 如果x_length较小，那么就需要 左→右 遍历中心剩余的行
            if(x_length < y_length) {
                for(; y < y_length - offset + 1; y++) {  // 需要注意y的边界条件
                    result.add(matrix[x][y]);
                }
            } 
            // 如果y_length较小，那么就需要 上→下 遍历中心剩余的列
            else {
                for(; x < x_length - offset + 1; x++) {  // 需要注意x的边界条件
                    result.add(matrix[x][y]);
                }
            }
        }

        return result;
    }
}

解题思路：模拟转圈遍历数字。关键在于对中心剩余数字的判定和遍历。

链表

【203】移除链表元素✔

题目链接：203. 移除链表元素 - 力扣（LeetCode）

题解：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 创建一个dummyHead，为了保证头节点和其他节点的处理方式一致，不用单独处理头节点
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode temp = dummyHead;

        while(temp.next != null) {
            if(temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}

注意这里的一个细节：设置dummyHead节点链接在头节点之前，使得头节点和其他节点的处理方式一致，不必再单独处理头节点。

【707】设计链表❗

题目链接：707. 设计链表 - 力扣（LeetCode）

题解一：

// 定义单链表的ListNode结构
class ListNode {
    int val;
    ListNode next;
    ListNode() {};
    ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    int size;  // size存储链表元素的个数
    ListNode head; // 定义虚拟头节点

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0); // 初始化虽然size为0，但是有一个虚拟头节点
    }
    
    public int get(int index) {
        // 先判断index是否合法
        if(index < 0 || index >= size) {
            return -1;
        }
        ListNode cur = head;
        // 包含一个虚拟头节点，因此需要找第 index+1 个节点（头节点的index为0）
        for(int i = 0; i <= index; i++) {
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        // 先判断index是否合法
        if(index > size) {
            return;
        }
        // 可以不判断 index < 0 的情况，样例都可以通过
        if(index < 0) {
            index = 0;
        }
        
        // 定义前驱节点
        ListNode pre = head;
        // 查找要插入节点的前驱
        for(int i = 0; i < index; i++) {
            pre = pre.next;
        }
        ListNode newNode = new ListNode(val);
        newNode.next = pre.next;
        pre.next = newNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        // 先判断index是否合法
        if(index < 0 || index >=size) {
            return;
        }
        // 查找要删除节点的前驱
        ListNode pre = head;
        for(int i = 0; i < index; i++) {
            pre = pre.next;
        }
        pre.next = pre.next.next;
        size--;
    }
}

采用单链表的设计思路，需要注意以下几点：

• 定义单链表的ListNode结构❗
• 初始化的时候size为0（表示没有节点），但是会存在一个虚拟头节点。因此在get()、addAtIndex()、deleteAtIndex()时需要注意for循环的条件。

题解二：

// 定义双链表的ListNode结构
class ListNode {
    int val;
    ListNode next;
    ListNode prev;
    ListNode() {};
    ListNode(int val) {
        this.val = val;
    }
}

class MyLinkedList {
    int size;  // size存储链表元素的个数
    ListNode head;  // 定义虚拟头节点
    ListNode tail;  // 定义尾节点

    public MyLinkedList() {
        size = 0;
        head = new ListNode();
        tail = new ListNode();
        // 双向链表注意链接首尾节点
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int index) {
        // 先判断index是否合法
        if(index < 0 || index >= size) {
            return -1;
        }
        ListNode cur; // 定义当前节点指针
        // 如果index在链表的前半部分，则从前往后查找
        if(index < size / 2) {
            cur = head;
            for(int i = 0; i <= index; i++) {
                cur = cur.next;
            }
        } 
        // 如果index在链表的后半部分，则从后往前查找
        else {
                cur = tail;
                for(int i = 0; i < size - index; i++) {
                    cur = cur.prev;
                }
            }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        // 先判断index是否合法
        if(index < 0 || index > size) {
            return;
        }

        ListNode newNode = new ListNode(val);
        // 如果index在链表的前半部分，则从前往后查找
        if(index < size / 2) {
            ListNode preNode = head;  // 定义前序节点指针
            for(int i = 0; i < index; i++) {
                preNode = preNode.next;
            }
            newNode.next = preNode.next;
            newNode.prev = preNode;
            preNode.next.prev = newNode;
            preNode.next = newNode;
        } 
        // 如果index在链表的后半部分，则从后往前查找
        else {
            ListNode postNode = tail;  // 定义后序节点指针
            for(int i = 0; i < size - index; i++) {
                postNode = postNode.prev;
            }
            newNode.next = postNode;
            newNode.prev = postNode.prev;
            postNode.prev.next = newNode;
            postNode.prev = newNode;
        }
        size++;
    }
    
    public void deleteAtIndex(int index) {
        // 先判断index是否合法
        if(index < 0 || index >= size) {
            return;
        }

        // 如果index在链表的前半部分，则从前往后查找
        if(index < size / 2) {
            ListNode preNode = head;  // 定义前序节点指针
            for(int i = 0; i < index; i++) {
                preNode = preNode.next;
            }
            preNode.next.next.prev = preNode;
            preNode.next = preNode.next.next;
        } 
        // 如果index在链表的后半部分，则从后往前查找
        else {
            ListNode postNode = tail;  // 定义后序节点指针
            for(int i = 0; i < size - index - 1; i++) {
                 postNode = postNode.prev;
            }
            postNode.prev.prev.next = postNode;
            postNode.prev = postNode.prev.prev;
        }
        size--;
    }
}

采用双向链表的设计思路，需要注意以下几点：

• 定义双向链表的ListNode结构❗
• 在get()、addAtIndex()、deleteAtIndex()时需要注意for循环的条件，以及首尾节点的初始化，还要注意操作节点时要同时改变前序指针和后序指针指向。

【206】反转链表

题目链接：206. 反转链表 - 力扣（LeetCode）

题解一：

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    // 将 当前节点 链接到 前一个节点
    public ListNode reverse(ListNode prev, ListNode cur) {
        if(cur == null) {
            return prev;
        }
        // 定义一个临时节点保存当前节点的下一个节点
        ListNode temp = cur.next;
        cur.next = prev;  // 反转操作
        // 将 当前节点的下一个节点 链接到 当前节点
        return reverse(cur, temp);
    }
}

递归思路：（从前往后）定义一个递归函数，目的是把当前节点链接到前一个节点上。

注意返回条件和返回值。

题解二：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;  // 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}

双指针写法。注意初始化和循环条件

【24】两两交换链表中的节点

题目链接：24. 两两交换链表中的节点 - 力扣（LeetCode）

题解一：

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode first = head;  // 定义当前节点
        ListNode second = first.next;  // 定义当前节点的下一个节点
        ListNode third = second.next;  // 定义下一对要反转的“头节点”
        // 反转操作
        second.next = first;
        first.next = swapPairs(third);  // 用third去接收下一对反转后的新的“头节点”
        return second;  // 返回当前节点的下一个节点，即反转后的头节点
    }
}

递归思路：把当前节点和当前节点的下一个节点看成一对。要理解swapPairs()的目的在于交换当前节点（first）和当前节点的下一个节点（second），返回下一个节点（second）。

题解二：

class Solution {
  public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 设置一个虚拟头结点
        dumyhead.next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode cur = dumyhead;
        ListNode temp; // 临时节点，保存两个节点后面的节点
        ListNode firstnode; // 临时节点，保存两个节点之中的第一个节点
        ListNode secondnode; // 临时节点，保存两个节点之中的第二个节点
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步骤一
            secondnode.next = firstnode; // 步骤二
            firstnode.next = temp;      // 步骤三
            cur = firstnode; // cur移动，准备下一轮交换
        }
        return dumyhead.next;  
    }
}

迭代法。

【19】删除链表的倒数第N个节点✔❗

题目链接：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

解法一：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 先遍历一次获得链表的长度
        int size = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            size++;
        }

        // 删除第n个节点
        ListNode dummyHead = new ListNode();  // 为了避免删除掉头节点的情况，定义一个虚拟头节点
        dummyHead.next = head;
        ListNode preNode = dummyHead;
        for(int i = 1; i <= size - n; i++) {
            preNode = preNode.next;
        }
        preNode.next = preNode.next.next;
        return dummyHead.next;
    }
}

很自然地想到先遍历一遍链表获得长度，再删除第N个节点。

解法二：❗

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //新建一个虚拟头节点指向head
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        //快慢指针指向虚拟头节点
        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i <= n; i++) {
            fastIndex = fastIndex.next;
        }
        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        // 此时 slowIndex 的位置就是待删除元素的前一个位置。
        // 检查 slowIndex.next 是否为 null，以避免空指针异常
        if (slowIndex.next != null) {
            slowIndex.next = slowIndex.next.next;
        }
        return dummyNode.next;
    }
}

双指针思路：由于需要找到倒数第N个节点，因此可以使用两个指针 fastIndex 和 slowIndex 同时对链表进行遍历，并且fastIndex比slowIndex 超前 N个节点。当fastIndex遍历到链表的末尾时，slowIndex就恰好处于倒数第N个节点。

【160】相交链表✔

题目链接：160. 相交链表 - 力扣（LeetCode）

题解：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 首先计算两个链表的长度
        int size_A = 0;
        int size_B = 0;
        ListNode cur_A = headA;
        ListNode cur_B = headB;
        while(cur_A != null) {
            cur_A = cur_A.next;
            size_A++;
        }
        while(cur_B != null) {
            cur_B = cur_B.next;
            size_B++;
        }

        // 确定较短的链表，赋给cur_short； 确定较长的链表，赋给cur_long
        ListNode cur_short;
        ListNode cur_long;
        if(size_A > size_B) {
            cur_short = headB;
            cur_long = headA;
        } else {
            cur_short = headA;
            cur_long = headB;
        }
        // 使链表尾部对其，移动长链表的差值部分
        for(int i = 1; i <= Math.abs(size_A - size_B); i++) {
            cur_long = cur_long.next;
        }
        // 循环判断是否有相同的节点
        while(cur_long != null && cur_short != null) {
            if(cur_long == cur_short) {
                return cur_long;
            }
            cur_long = cur_long.next;
            cur_short = cur_short.next;
        }

        return null;
    }
}

对齐两个链表的尾部，长链表需要提前移动和短链表的长度差，然后从两个链表同时出发进行比较。

【142】环形链表❗

题目链接：142. 环形链表 II - 力扣（LeetCode）

题解：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        // 一定是用fast去作为循环的判断条件
        while(fast != null && fast.next != null) {
            slow = slow.next;  // slow每次移动一步
            fast = fast.next.next;  // fast每次移动两步
            // 相遇及说明有环
            if(slow == fast) {
                ListNode index1 = head;  // 一个从链表头节点开始
                ListNode index2 = slow;  // 一个从相遇节点开始
                // 两个指针每次移动一步，相遇节点即为入环的第一个节点
                while(index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        // 如果跳出了循环，则说明无环
        return null;
    }
}

快慢指针思路。fast快指针从头出发，每次移动两步，slow慢指针从头出发，每次移动一步。直到快慢指针相遇，同时从相遇节点（index2）和链表头节点（index1）出发每次移动一步，直到相遇即为入环的第一个节点。

需要注意最外侧的循环条件。❗

哈希表

【242】有效的字母异位词✔❗

题目链接：242. 有效的字母异位词 - 力扣（LeetCode）

题解：

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] result = new int[26];  // 创建26长度大小的数组result，用于记录字母a-z的次数
        char[] s_list = s.toCharArray();
        char[] t_list = t.toCharArray();

        // 遍历s，在result中记录遇到的字母，加一操作
        for(int i = 0; i < s_list.length; i++) {
            result[s_list[i] - 'a'] += 1;  // 注意表达
        }
        // 遍历t，在result中记录遇到的字母，减一操作
        for(int i = 0; i < t_list.length; i++) {
            result[t_list[i] - 'a'] -= 1;  // 注意表达
        }
        // 如果达到题目要求，则result应为全0状态
        for(int i = 0; i < result.length; i++) {
            if(result[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

哈希的思路，但是用数组解决。

注意[character - 'a']的表达❗

【383】赎金信✔

题目链接：383. 赎金信 - 力扣（LeetCode）

题解：

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] result = new int[26];  // 创建26长度大小的数组result，用于记录字母a-z的次数
        char[] ransomNote_list = ransomNote.toCharArray();
        char[] magazine_list = magazine.toCharArray();

        // 遍历magazine_list，在result中记录遇到的字母，加一操作
        for(int i = 0; i < magazine_list.length; i++) {
            result[magazine_list[i] - 'a'] += 1;  // 注意表达
        }
        // 遍历ransomNote_list，在result中记录遇到的字母，减一操作
        for(int i = 0; i < ransomNote_list.length; i++) {
            result[ransomNote_list[i] - 'a'] -= 1;  // 注意表达
        }
        // 如果达到题目要求，则result应为全部大于0的状态
        for(int i = 0; i < result.length; i++) {
            if(result[i] < 0) {
                return false;
            }
        }
        return true;
    }
}

同【242】有效的字母异位词（242. 有效的字母异位词 - 力扣（LeetCode））解题思路一致。哈希的思路，但是用数组解决。

【49】字母异位词分组✔❗

题目链接：49. 字母异位词分组 - 力扣（LeetCode）

题解：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 创建哈希表map，每一个entry的Key是排序后的str，其值是一个List<String>，用于存储Key的字母异位词
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            char[] array = str.toCharArray(); // 将str转化为字符数组
            Arrays.sort(array);  // 排序
            String key = new String(array);  // 得到排序后的字符串，作为Key
            List<String> list = map.getOrDefault(key, new ArrayList<String>());  // 简化写法
            list.add(str);
            map.put(key, list);
        }
        List<List<String>> result = new ArrayList<List<String>>(map.values());  // 简化写法
        return result;
    }
}

利用哈希的解题关键：由于是字母异位词，那么每个字母异位词排序后是相同的。

创建Map，每一个entry的Key是排序后的字符串str，其值是一个List<String>，用于存储Key的字母异位词，最后用一个结果接收。

注意：❗

• String key = new String(array)将字符数组array转化为字符串
• map.values()可以返回所有value值构成的数组

【438】找到字符串中所有字母异位词✔❗

题目链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

题解：

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int s_len = s.length();
        int p_len = p.length();
        List<Integer> result = new ArrayList<>();
        // 如果s的长度小于p的长度，直接返回result
        if(s_len < p_len) {
            return result;
        }

        // 构建两个数组存放字符串中字母出现的词频，并以此作为标准比较
        int[] s_count = new int[26];
        int[] p_count = new int[26];

        // 初始化滑动窗口
        for(int i = 0; i < p_len; i++) {
            s_count[s.charAt(i) - 'a'] += 1;  // 记录s中前p_len个字母的词频（每次窗口向前滑动时，更新该数组）
            p_count[p.charAt(i) - 'a'] += 1;  // 记录要寻找的字符串p中每个字母的词频（只记录这一次，作为判断标准）
        }
        // 对初始滑动窗口进行判断
        if(Arrays.equals(s_count, p_count)) {  // 注意快速判断写法
            result.add(0);
        }

        // 窗口开始滑动
        for(int i = 0; i < s_len - p_len; i++) {
            s_count[s.charAt(i) - 'a'] -= 1;  // 将左边界向右移动一位
            s_count[s.charAt(i + p_len) - 'a'] += 1; // 将右边界向右移动一位
            // 每滑动一次，就进行判断
            if(Arrays.equals(s_count, p_count)) {  // 注意快速判断写法
                result.add(i + 1);
            }
        }
        return result;
    }
}

利用滑动窗口依次进行判断，用字符数组代替哈希记录字符串中字母出现的词频，进行比较。

注意：❗

• 快速比较两个数组是否相同：Arrays.equals(s_count, p_count)
• 获取字符串中指定下标的字母：s.charAt(i)

【349】两个数组的交集✔❗

题目链接：349. 两个数组的交集 - 力扣（LeetCode）

题解：

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> record = new HashSet<>();
        Set<Integer> res_set = new HashSet<>();
        // 遍历nums1，记录出现的数字
        for(int i : nums1) {
            record.add(i);
        }
        // 遍历nums2，如果存在于record，则添加至res_set
        for(int i : nums2) {
            if(record.contains(i)) {
                res_set.add(i);
            }
        }

        return res_set.stream().mapToInt(x -> x).toArray();  //stream()的快速返回写法
    }
}

由于返回的结果是去重的，因此考虑Set()。

注意：❗

• stream()的快速返回写法：res_set.stream().mapToInt(x -> x).toArray()

【350】两个数组的交集Ⅱ✔

题目链接：350. 两个数组的交集 II - 力扣（LeetCode）

题解：

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // 定义Map集合，分别记录数组中出现的元素以及出现的次数
        Map<Integer, Integer> record_num1 = new HashMap<>();
        Map<Integer, Integer> record_num2 = new HashMap<>();
        // 遍历nums1，记录nums1中出现的元素及其次数
        for(int i : nums1) {
            record_num1.put(i, record_num1.getOrDefault(i, 0) + 1);
        }
        // 遍历nums2，记录nums2中出现的元素及其次数
        for(int i : nums2) {
            record_num2.put(i, record_num2.getOrDefault(i, 0) + 1);
        }
        // 定义list用于接收返回值
        List<Integer> list = new ArrayList<>();

        // 遍历record_num1
        for(Map.Entry<Integer, Integer> entry : record_num1.entrySet()) {
            // 如果record_num2中有record_num1中的元素，根据出现的最小次数添加至list 
            if(record_num2.containsKey(entry.getKey())) {
                // 记录交集元素的最小出现频次
                int count = Math.min(entry.getValue(), record_num2.get(entry.getKey()));
                for(int i = 0; i < count; i++) {
                    list.add(entry.getKey());  // 添加
                }
            }
        }

        return list.stream().mapToInt(x -> x).toArray();  //stream()的快速返回写法
    }
}

由于涉及公共元素出现的最小次数，考虑使用Map()

【202】快乐数✔❗

题目链接：202. 快乐数 - 力扣（LeetCode）

题解：

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while(n != 1) {
            record.add(n);
            n = sum(n);
            if(record.contains(n)) {
                return false;
            }
        }
        return true;
    }

    public int sum(int n) {
        int sum = 0;
        while(n > 0) {
            int ge = n % 10;
            sum += ge * ge;
            n = n / 10;
        }
        return sum;
    }
}

解题关键：题目中说了会无限循环，那么也就是说求和的过程中，sum会重复出现❗

【1】两数之和✔

题目链接：1. 两数之和 - 力扣（LeetCode）

题解：

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if(nums == null || nums.length == 0){
            return res;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];   // 遍历当前元素，并在map中寻找是否有匹配的key
            if(map.containsKey(temp)){
                res[1] = i;
                res[0] = map.get(temp);
                break;
            }
            map.put(nums[i], i);    // 如果没找到匹配对，就把访问过的元素和下标加入到map中
        }
        return res;
    }
}

用哈希的方法要快一些。

【454】四数相加Ⅱ

题目链接：454. 四数相加 II - 力扣（LeetCode）

题解：

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        int result = 0;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                int sum = i + j;
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                int sum = i + j;
                result += map.getOrDefault(0 - sum, 0);
            }
        }
        return result;
    }
}

利用哈希表，先统计前两个数组的排列组合的和，并统计出现的次数，再统计后两个数组的排列组合的和，如果四数之和为0，那么更新result

【15】三数之和❗

题目链接：15. 三数之和 - 力扣（LeetCode）

题解：

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> set = new HashSet<>();  // 定义set集合做去重操作
        Arrays.sort(nums);  // 对原始数组排序（关键）
        for(int i = 0; i < nums.length - 2; i++) {  // 定义i指针在最左侧，不停遍历向右移动
            int left = i + 1;  // 定义left指针在i指针右侧加一位置，根据sum的大小调节移动
            int right = nums.length - 1;  // 定义right指针在最右侧，根据sum的大小调节移动
            while(left < right) {
                // sum一定要写到循环里面
                int sum = nums[i] + nums[left] + nums[right];
                // 如果sum < 0，向右移动left指针
                if(sum < 0) {
                    left++;
                } 
                // 如果sum > 0，向左移动right指针
                else if(sum > 0) {
                    right--;
                }
                // 如果sum == 0，收获结果
                else {
                    List<Integer> res = Arrays.asList(nums[i], nums[left], nums[right]);
                    // Collections.sort(res);  // 对每一个结果可以不排序
                    set.add(res); // 对结果去重
                    left++;
                    right--;
                }
            }
        }
        // 将去重结果添加至result集合中
        List<List<Integer>> result = new ArrayList<>();
        for(List<Integer> item : set) {
            result.add(item);
        }
        return result;
    }
}

解题思路：双指针 + 哈希去重。

首先对原始数组排序（关键），然后在for循环定义最左侧指针i，在循环内部：定义指针left = i + 1和指针right = nums.length - 1，随着sum和目标结果（0）的关系移动left和right指针。利用set集合对结果进行去重。

注意：❗

• 对数组排序：Arrays.sort(nums)
• 对集合排序：Collections.sort(res)

【18】四数之和✔

题目链接：18. 四数之和 - 力扣（LeetCode）

题解：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Set<List<Integer>> set = new HashSet<>();  // 定义set集合做去重操作
        Arrays.sort(nums);  // 对原始数组排序（关键）
        for(int i = 0; i < nums.length - 3; i++) {  // 定义i指针在最左侧，不停遍历向右移动
            for(int j = i + 1; j < nums.length - 2; j++) {  // 定义j指针为i+1，不停遍历向右移动
                int left = j + 1;  // 定义left指针在j指针右侧加一位置，根据sum的大小调节移动
                int right = nums.length - 1;  // 定义right指针在最右侧，根据sum的大小调节移动
                while(left < right) {
                    // sum一定要写到循环里面
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];  // 注意本题会有溢出样例
                    if(sum < target) {
                        left++;
                    }
                    else if(sum > target) {
                        right--;
                    }
                    else {
                        List<Integer> res = Arrays.asList(nums[i], nums[j], nums[left], nums[right]);
                        // Collections.sort(res);  // 对每一个结果可以不排序
                        set.add(res);
                        left++;
                        right--;
                    }
                }
            }
        }
        // 将去重结果添加至result集合中
        List<List<Integer>> result = new ArrayList<>();
        // List<List<Integer>> result = new ArrayList<>();
        for(List<Integer> item : set) {
            result.add(item);
        }
        return result;
    }
}

解题思路：双指针 + 哈希去重。（同【15】三数之和（15. 三数之和 - 力扣（LeetCode））一样）

字符串

【344】反转字符串✔❗

题目链接：344. 反转字符串 - 力扣（LeetCode）

题解一：

class Solution {
    public void reverseString(char[] s) {
        int count = s.length / 2;
        for(int i = 0; i < count; i++) {
            char temp = s[i];
            s[i] = s[s.length - i - 1];
            s[s.length - i - 1] = temp;
        }
    }
}

很简单，两两交换位置。注意下标。

题解二：

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

个人更推荐这种方式，下标不容易出错。❗

【541】反转字符串Ⅱ❗

题目链接：541. 反转字符串 II - 力扣（LeetCode）

题解：

class Solution {
    public String reverseStr(String s, int k) {
        char[] s_list = s.toCharArray();
        for(int i = 0; i < s.length(); i += 2 * k) {  // 循环周期：2k
            //关键：反转长度为k的子串，若剩余子串长度不足 k，则反转整个子串。
            reverse(s_list, i, Math.min(i + k, s.length()) - 1);  
        }
        return new String(s_list);
    }
    
    public void reverse(char[] arr, int left, int right) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

思路❗：反转每个下标从 2k 的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串。

【151】反转字符串中的单词✔❗

题目链接：151. 反转字符串中的单词 - 力扣（LeetCode）

题解：

class Solution {
    public String reverseWords(String s) {
        Stack<Character> stack_str = new Stack<>();  // 用于处理整个字符串
        Stack<Character> stack_word = new Stack<>();  // 用于处理单词
        String new_s = s.trim();  // 去除字符串首尾空格
        char[] s_list = new_s.toCharArray();  
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s_list.length; i++) {
            // 字符串中间连续空格跳过
            if(s_list[i] == ' ' && s_list[i + 1] == ' ') {
                continue;
            }
            stack_str.push(s_list[i]);  // 将处理过后的字符串入栈（首尾无空格，单词之间只有一个空格）
        }

        while(!stack_str.isEmpty()) {
            // 如果stack_str栈顶为字母，那就将其添加至stack_word
            if(stack_str.peek() != ' ') {
                stack_word.push(stack_str.pop());
            } 
            // 如果stack_str栈顶为空格，那就弹出stack_word（一个单词）
            else {
                while(!stack_word.isEmpty()) {
                    sb.append(stack_word.pop());
                }
                sb.append(' ');
                stack_str.pop();
            }
        }
        // 添加最后一个单词
        while(!stack_word.isEmpty()) {
            sb.append(stack_word.pop());
        }
        return sb.toString();
    }
}

思路：利用两个栈处理，一个栈stack_str用于添加整个字符串，另一个栈stack_word用于处理单词。

关键在于字符串空格的处理❗：

• 去除字符串首尾空格trim()：String new_s = s.trim();
• 处理字符串中间连续的空格。

【28】找出字符串中第一个匹配项的下标✔

题目链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

题解：

class Solution {
    public int strStr(String haystack, String needle) {
        char[] haystack_list = haystack.toCharArray();
        char[] needle_list = needle.toCharArray();
        for(int i = 0; i <= haystack_list.length - needle_list.length; i++) {
            int index = i;
            boolean flag = true;
            for(int j = 0; j < needle_list.length; j++) {
                if(needle_list[j] != haystack_list[index]) {
                    flag = false;
                    break;
                }
                index++;
            }
            if(flag == true) {
                return i;
            }
        }
        return -1;
    }
}

暴力解法。还可以使用KMP算法。

【459】重复的子字符串

题目链接：459. 重复的子字符串 - 力扣（LeetCode）

题解：

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        char[] s_list = s.toCharArray();
        for(int i = 0; i < s_list.length / 2; i++) {  // 子串最大长度为原字符串长度的一半
            if(judge(s_list, i)) {
                return true;
            }
        }
        return false;
    }

    // 判断子串是否可以构成原字符串
    public boolean judge(char[] s_list, int sub_end) {
        // 如果子串长度不能被原字符串长度整除，直接返回false
        if(s_list.length % (sub_end + 1) != 0) {
            return false;
        }
        // 子串起始下标为sub_start = 0（子串结束下标为sub_end）
        int sub_start = 0;
        for(int i = sub_end + 1; i < s_list.length; i++) {  // 从sub_end + 1开始
            // 如果子串不能匹配，直接返回false
            if(s_list[sub_start % (sub_end + 1)] != s_list[i]) {
                return false;
            }
            sub_start++;
        }
        return true;
    }
}

暴力解法，也可以使用KMP算法。

栈与队列

【232】用栈实现队列✔

题目链接：232. 用栈实现队列 - 力扣（LeetCode）

题解：

class MyQueue {
    Stack<Integer> stack_in;  // 用于存储数据
    Stack<Integer> stack_out;  // 用于取数据

    public MyQueue() {
        stack_in = new Stack<>();
        stack_out = new Stack<>();
    }
    
    public void push(int x) {
        stack_in.push(x);
    }
    
    public int pop() {
        // 将stack_in的数据导入stack_out
        while(!stack_in.isEmpty()) {
            stack_out.push(stack_in.pop());
        }
        int result = stack_out.pop();  // 取结果
        // 再将stack_out的数据导回stack_in
        while(!stack_out.isEmpty()) {
            stack_in.push(stack_out.pop());
        }
        return result;
    }
    
    public int peek() {
        // 将stack_in的数据导入stack_out
        while(!stack_in.isEmpty()) {
            stack_out.push(stack_in.pop());
        }
        int result = stack_out.peek();  // 取结果
        // 再将stack_out的数据导回stack_in
        while(!stack_out.isEmpty()) {
            stack_in.push(stack_out.pop());
        }
        return result;
    }
    
    public boolean empty() {
        return stack_in.isEmpty();
    }
}

利用两个栈结构实现

【225】用队列实现栈✔❗

题目链接：225. 用队列实现栈 - 力扣（LeetCode）

题解：

class MyStack {
    int size;  // 需要size记录数量
    Queue<Integer> queue_in;  // 用于存储数据
    Queue<Integer> queue_out;  // 用于取数据

    public MyStack() {
        queue_in = new LinkedList<>();  // 注意初始化
        queue_out = new LinkedList<>();  // 注意初始化
    }
    
    public void push(int x) {
        queue_in.add(x);
        size++;
    }
    
    public int pop() {
        // 将queue_in的数据导入queue_out，还剩一个
        for(int i = 0; i < size - 1; i++) {
            queue_out.add(queue_in.poll());
        }
        int result = queue_in.poll();  // queue_in中剩余的一个就是目标值
        // 再将queue_out的数据导回queue_in
        while(!queue_out.isEmpty()) {
            queue_in.add(queue_out.poll());
        }
        size--;
        return result;
    }
    
    public int top() {
        // 将queue_in的数据导入queue_out，还剩一个
        for(int i = 0; i < size - 1; i++) {
            queue_out.add(queue_in.poll());
        }
        int result = queue_in.peek();  // queue_in中剩余的一个就是目标值
        queue_out.add(queue_in.poll());  // queue_in中剩余的再添加至queue_out中
        // 再将queue_out的数据导回queue_in
        while(!queue_out.isEmpty()) {
            queue_in.add(queue_out.poll());
        }
        return result;
    }
    
    public boolean empty() {
        return queue_in.isEmpty();
    }
}

注意❗：

• 需要有一个size记录数量，方便取队列的最后一个值
• 队列的初始化：Queue<Integer> queue_in = new LinkedList<>();
• LinkedList结构：添加元素方法：add()；弹出元素方法：poll()

【20】有效的括号✔

题目链接：20. 有效的括号 - 力扣（LeetCode）

题解：

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        char[] s_list = s.toCharArray();
        // 遍历字符串
        for(int i = 0; i < s_list.length; i++) {
            // 如果当前字符为左括号，直接入栈
            if(s_list[i] == '(' || s_list[i] == '[' || s_list[i] == '{') {
                stack.push(s_list[i]);
            }
            // 如果当前字符为右括号，需要弹栈
            else {
                // 如果小括号匹配，则继续（需要提前判断栈是否为空）
                if(!stack.isEmpty() && s_list[i] == ')' && stack.pop() == '(') {
                    continue;
                }
                // 如果中括号匹配，则继续（需要提前判断栈是否为空）
                else if(!stack.isEmpty() && s_list[i] == ']' && stack.pop() == '[') {
                    continue;
                }
                // 如果大括号匹配，则继续（需要提前判断栈是否为空）
                else if(!stack.isEmpty() && s_list[i] == '}' && stack.pop() == '{') {
                    continue;
                }
                // 上述条件都不满足，直接返回false
                else {
                    return false;
                }
            }
        }
        return stack.isEmpty();  // 如果栈不为空，则说明还有没匹配到的括号，返回false
    }
}

利用栈解决，遍历字符串，如果是左括号，直接入栈；如果是右括号，需要弹栈判断。

【1047】删除字符串中的所有相邻重复项✔❗

题目链接：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

题解：

class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        char[] s_list = s.toCharArray();
        for(int i = 0; i < s_list.length; i++) {
            // 如果栈为空，直接入栈
            if(stack.isEmpty()) {
                stack.push(s_list[i]);
            }
            // 如果栈不为空，则要判断
            else {
                // 如果当前元素等于栈顶元素，则弹栈
                if(s_list[i] == stack.peek()) {
                    stack.pop();
                    continue;
                } 
                // 如果当前元素不等于栈顶元素，则当前元素入栈
                else {
                    stack.push(s_list[i]);
                }
            }
        }
        // 返回结果
        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.insert(0, stack.pop());
        }
        return sb.toString();
    }
}

注意❗：StringBuilder的插入方法：sb.insert(0, stack.pop());

【150】逆波兰表达式求值✔❗

题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

题解：

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        for(int i = 0; i < tokens.length; i++) {
            // 如果不是运算符，直接入栈
            if(!tokens[i].equals("+") && !tokens[i].equals("-") && !tokens[i].equals("*") && !tokens[i].equals("/")) {
                stack.push(tokens[i]);
            }
            else if(tokens[i].equals("+")) {
                int x = Integer.parseInt(stack.pop());
                int y = Integer.parseInt(stack.pop());
                stack.push((y + x) + "");  
            }
            else if(tokens[i].equals("-")) {
                int x = Integer.parseInt(stack.pop());
                int y = Integer.parseInt(stack.pop());
                stack.push((y - x)  + "");  // 需要注意y在前
            }
            else if(tokens[i].equals("*")) {
                int x = Integer.parseInt(stack.pop());
                int y = Integer.parseInt(stack.pop());
                stack.push((y * x) + "");
            }
            else if(tokens[i].equals("/")) {
                int x = Integer.parseInt(stack.pop());
                int y = Integer.parseInt(stack.pop());
                stack.push((y / x) + "");  // 需要注意y在前
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

利用栈解决。

注意❗：

• 字符串比较：tokens[i].equals("+")
• 字符串转化为数字：Integer.parseInt(stack.pop());

【239】滑动窗口的最大值❗

题目链接：239. 滑动窗口最大值 - 力扣（LeetCode）

题解：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 双端队列结构Deque，允许在队列两端进行操作
        // 队首到队尾的元素保证单调减小
        Deque<Integer> deque = new LinkedList<>();  
        int[] result = new int[nums.length - k + 1];  // 记录最后的结果
        // 还未形成滑动窗口
        for(int i = 0; i < k; i++) {  // 循环的长度等于窗口长度
            // 如果当前待添加的元素大于队尾的元素，则循环删除队尾元素
            while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);  // 将当前元素添加至队尾
        }
        result[0] = deque.getFirst();  // 取第一个结果（队首元素始终是滑动窗口内的最大元素）

        // 已形成滑动窗口
        for(int i = k; i < nums.length; i++) {
            // 需要判断：如果队首元素为滑动窗口的第一个值，由于需要向前滑动，需要将其删去（与未形成滑动窗口的区别）
            if(deque.peekFirst() == nums[i - k]) {
                deque.removeFirst();
            }
            // 如果当前待添加的元素大于队尾的元素，则循环删除队尾元素
            while(!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            deque.addLast(nums[i]);  // 将当前元素添加至队尾
            result[i - k + 1] = deque.getFirst();  // 取结果（队首元素始终是滑动窗口内的最大元素）
        }
        return result;
    }
}

暴力解法超时

思路：需要利用双端队列结构维持一个单调减的滑动窗口，队首始终为滑动窗口的最大值。关键点在于，如果当前添加的元素大于滑动窗口内队首方向的其他元素，则需要将其他元素删除（没有维护的必要）。更详细的思路参考：代码随想录

注意❗：

• 双端队列结构Deque：Deque<Integer> deque = new LinkedList<>();
• Deque的常用方法：
  • addFirst(E e)：在队列头部插入元素
  • addLast(E e)：在队列尾部插入元素
  • removeFirst()：移除并返回队列头部的元素
  • removeLast()：移除并返回队列尾部的元素
  • getFirst()：获取但不移除队列头部的元素
  • getLast()：获取但不移除队列尾部的元素

【347】前K个高频元素❗

题目链接：347. 前 K 个高频元素 - 力扣（LeetCode）

题解：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();  // key存储nums数组中的元素，value存储频率
        for(int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);  // 利用优先级队列实现大根堆
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int[] temp = new int[2];  // 定义数组，0下标存储元素，1下标存储频率
            temp[0] = entry.getKey();
            temp[1] = entry.getValue();
            pq.add(temp);
        }
        int[] result = new int[k];  // 定义result数组，用于存储大根堆中前k个元素
        for(int i = 0; i < result.length; i++) {
            result[i] = pq.poll()[0];
        }
        return result;
    }
}

思路：利用大根堆解决。首先创建Map集合用于记录nums中出现的元素及其频率。利用优先级队列实现大根堆，将Map中的entry转化为int数组进行排序存储，最后前k个元素就是目标结果。

注意❗：利用优先级队列实现堆：

• 大根堆：PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1 - o2);
• 小根堆：PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o2 - o1);

二叉树

【144】二叉树的前序遍历✔❗

题目链接：144. 二叉树的前序遍历 - 力扣（LeetCode）

题解（递归）：

class Solution {
    List<Integer> result = new ArrayList<>(); // 创建result用于收集结果
    
    public List<Integer> preorderTraversal(TreeNode root) {
        recur(root);
        return result;
    }
    
    public void recur(TreeNode root) {
        if(root == null) {
            return;
        }
        result.add(root.val);  // 处理中间节点（收集结果）
        recur(root.left);  // 递归处理左节点
        recur(root.right);  // 递归处理右节点
    }
}

递归法

题解（迭代）❗：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>(); // 创建result用于收集结果
        if(root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);  // 根节点先入栈
        while(!stack.isEmpty()) {
            // 弹栈并收集结果
            TreeNode node = stack.pop();
            result.add(node.val);
            // 注意前序遍历要先将右节点入栈
            if(node.right != null) {
                stack.push(node.right);
            }
            // 然后将左节点入栈
            if(node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }
}

需要使用栈结构来实现迭代法。需要注意的是二叉树的前序遍历在入栈操作时要先处理右节点❗

【94】二叉树的中序遍历✔❗

题目链接：94. 二叉树的中序遍历 - 力扣（LeetCode）

题解（递归）：

class Solution {
    List<Integer> result = new ArrayList<>(); // 创建result用于收集结果

    public List<Integer> inorderTraversal(TreeNode root) {
        recur(root);
        return result;
    }

    public void recur(TreeNode root) {
        if(root == null) {
            return;
        }
        recur(root.left);  // 递归处理左节点
        result.add(root.val);  // 处理中间节点（收集结果）
        recur(root.right);  // 递归处理右节点
    }
}

题解（迭代）❗：

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>(); // 创建result用于收集结果
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;  // 利用cur指针来控制访问顺序
        while (cur != null || !stack.isEmpty()){
            // 如果cur不为空，则将cur入栈，并将cur重新指向其左节点
           if (cur != null){
               stack.push(cur);
               cur = cur.left;
           }
           // 如果cur为空，则弹栈，并将cur指向弹出节点，收集结果。最后将cur重新指向其右节点
           else{
               cur = stack.pop();
               result.add(cur.val);
               cur = cur.right;
           }
        }
        return result;
    }
}

注意中序遍历的迭代法和前序以及后序遍历的区别❗ 需要利用指针控制节点访问顺序。

【145】二叉树的后序遍历✔❗

题目链接：145. 二叉树的后序遍历 - 力扣（LeetCode）

题解（递归）：

class Solution {
    List<Integer> result = new ArrayList<>(); // 创建result用于收集结果

    public List<Integer> postorderTraversal(TreeNode root) {
        recur(root);
        return result;
    }

    public void recur(TreeNode root) {
        if(root == null) {
            return;
        }
        recur(root.left);  // 递归处理左节点
        recur(root.right);  // 递归处理右节点
        result.add(root.val);  // 处理中间节点（收集结果）
    }
}

题解（迭代）❗：

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>(); // 创建result用于收集结果
        if(root == null) {
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            // 弹栈并收集结果
            TreeNode node = stack.pop();
            result.add(node.val);
            // 注意后序遍历要先将左节点入栈
            if(node.left != null) {
                stack.push(node.left);
            }
            // 然后将右节点入栈
            if(node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(result);  // 利用Collections翻转数组
        return result;
    }
}

后序遍历的入栈顺序和前序遍历相反，最后还需要反转数组。

注意❗：利用Collections翻转数组：Collections.reverse(result);

【102】二叉树的层序遍历❗

题目链接：102. 二叉树的层序遍历 - 力扣（LeetCode）

题解：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();  // 用于收集最终结果
        if(root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();  // 利用队列实现层序遍历
        queue.add(root);  // 首先加入根节点
        // 最外层循环条件：队列不为空
        while(!queue.isEmpty()) {
            int count = queue.size();  // 记录当前队列中的元素个数（每一层的元素数量）
            List<Integer> list = new ArrayList<>();  // 用于收集每层的结果
            // 内层循环条件：count大于0
            // 逐个弹出节点，并收集结果，然后添加被弹出节点的左右节点
            while(count > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
            result.add(list);  // 收集每层结果
        }
        return result;
    }
}

以上是层序遍历的标准模板❗（利用队列实现）

【107】二叉树的层序遍历Ⅱ✔❗

题目链接：107. 二叉树的层序遍历 II - 力扣（LeetCode）

题解：

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> list = new ArrayList<>();
            while(count > 0) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
            result.add(0, list);  // 收集每层的结果时插入到0位置
        }
        return result;
    }
}

整体思路同基础的层序遍历一样，需要注意的是最后收集结果。

注意：ArrayList插入方法：result.add(0, list);

【199】二叉树的右视图✔

题目链接：199. 二叉树的右视图 - 力扣（LeetCode）

题解：

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            while(count > 0) {
                TreeNode node = queue.poll();
                // 如果该节点是当前层的最后一个节点，那么收集结果。
                if(count == 1) {
                    result.add(node.val);
                }
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
        }
        return result;
    }
}

整体思路同基础的层序遍历一样，就是需要在内层循环中，判断当前弹出节点是否是该层的最后一个节点，如果是，则收集结果；如果不是则略过。

【637】二叉树的层平均值✔

题目连接：637. 二叉树的层平均值 - 力扣（LeetCode）

题解：

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            double layer_sum = 0.0;
            // 为了在计算平均值时继续使用count，这里用for循环
            for(int i = 0; i < count; i++) {
                TreeNode node = queue.poll();
                layer_sum += node.val;
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            result.add(layer_sum / count);  // 计算平均值，收集结果
        }
        return result;
    }
}

整体思路同基础的层序遍历一样，需要注意在计算平均值时继续使用count，内层循环用for循环

【429】N叉树的层序遍历✔

题目链接：429. N 叉树的层序遍历 - 力扣（LeetCode）

题解：

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            List<Integer> list = new ArrayList<>();  // 用来收集每层的结果
            while(count > 0) {
                Node node = queue.poll();
                list.add(node.val);
                // 如果被弹出的节点有子节点，就将子节点全部添加至队列
                if(node.children != null) {
                    List<Node> children_list = node.children;
                    for(Node children_node : children_list) {
                        queue.add(children_node);
                    }
                }
                count--;
            }
            result.add(list);  // 添加每层的结果
        }
        return result;
    }
}

整体思路同基础的层序遍历一样，就是在处理子节点时为一个集合。

【515】在每个树行中找最大值✔

题目链接：515. 在每个树行中找最大值 - 力扣（LeetCode）

题解：

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            int max = Integer.MIN_VALUE;
            while(count > 0) {
                TreeNode node = queue.poll();
                max = max < node.val ? node.val : max;  // 取每层的最大值
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
            result.add(max);  // 收集结果
        }
        return result;
    }
}

整体思路同基础的层序遍历一样，就是在处理每层时取最大值。

【116】填充每个节点的下一个右侧节点指针✔

题目链接：116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

题解：

class Solution {
    public Node connect(Node root) {
        if(root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            List<Node> list = new ArrayList<>();  // 用于存储每一层的节点
            for(int i = 0; i < count; i++) {
                Node node = queue.poll();
                list.add(node);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            // 处理每一层的节点
            for(int i = 0; i < count - 1; i++) {
                list.get(i).next = list.get(i + 1);  // 使前一个节点的指针指向后一个节点
            }
            list.get(count - 1).next = null;  // 单独处理每一层的最后一个节点
        }
        return root;
    }
}

整体思路同基础的层序遍历一样。需要用一个集合来临时存储每一层节点，然后遍历该集合使得前一个节点的指针指向后一个节点，最后单独处理每层的最后一个节点。

【117】填充每个节点的下一个右侧节点指针Ⅱ✔

题目链接：117. 填充每个节点的下一个右侧节点指针 II - 力扣（LeetCode）

题解：

class Solution {
    public Node connect(Node root) {
        if(root == null) {
            return null;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            List<Node> list = new ArrayList<>();  // 用于存储每一层的节点
            for(int i = 0; i < count; i++) {
                Node node = queue.poll();
                list.add(node);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            // 处理每一层的节点
            for(int i = 0; i < count - 1; i++) {
                list.get(i).next = list.get(i + 1);  // 使前一个节点的指针指向后一个节点
            }
            list.get(count - 1).next = null;  // 单独处理每一层的最后一个节点
        }
        return root;
    }
}

同116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）解法一样。

【104】二叉树的最大深度✔

题目链接：104. 二叉树的最大深度 - 力扣（LeetCode）

题解（BFS）：

class Solution {
    public int maxDepth(TreeNode root) {
        int depth = 0;
        if(root == null) {
            return depth;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            depth++;  // 只要没退出循环，每一轮循环就加深一层
            while(count > 0) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
        }
        return depth;
    }
}

整体思路同基础的层序遍历一样。最外侧的循环，每循环一次，表示深一层。

题解（DFS）：

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left_depth = maxDepth(root.left);
        int right_depth = maxDepth(root.right);
        return Math.max(left_depth, right_depth) + 1;
    }
}

利用递归实现深度优先搜索。

【111】二叉树的最小深度✔❗

题目链接：111. 二叉树的最小深度 - 力扣（LeetCode）

题解（BFS）：

class Solution {
    public int minDepth(TreeNode root) {
        int depth = 0;
        if(root == null) {
            return depth;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            depth++; // 每循环一次，表示更深一层
            while(count > 0) {
                TreeNode node = queue.poll();
                // 如果遇到一个节点无左右子节点，则该层就是最小深度，直接返回
                if(node.left == null && node.right == null) {
                    return depth;
                }
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
        }
        return depth;
    }
}

整体思路同基础的层序遍历一样。如果遇到一个节点无左右子节点，则该层就是最小深度，直接返回。

题解（BFS）❗：

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 计算左子树的深度
        int left_depth = minDepth(root.left);
        // 计算右子树的深度
        int right_depth = minDepth(root.right);
        // 如果左子树或右子树的深度不为 0，即存在一个子树，那么当前子树的最小深度就是该子树的深度+1
        if(left_depth == 0 || right_depth == 0) {
            return left_depth + right_depth + 1;  // 相当于 left_depth + 1 或 right_depth + 1
        }
        // 如果左子树和右子树的深度都不为 0，即左右子树都存在，那么当前子树的最小深度就是它们较小值+1
        else {
            return Math.min(left_depth, right_depth) + 1;
        }
    }
}

利用递归实现深度优先搜索。注意返回的条件❗

【226】翻转二叉树✔

题目链接：226. 翻转二叉树 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        // 操作当前节点，翻转当前节点的左右节点
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // 递归对左右节点进行进一步翻转
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

递归实现。

【101】对称二叉树

题目链接：101. 对称二叉树 - 力扣（LeetCode）

题解：

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right) {
        if(left == null && right != null) {
            return false;
        }
        if(left != null && right == null) {
            return false;
        }
        if(left == null && right == null) {
            return true;
        }
        if(left.val != right.val) {
            return false;
        }
        boolean compare_outside = compare(left.left, right.right);  // 比较外侧
        boolean compare_inside = compare(left.right, right.left);  // 比较内测
        return compare_outside && compare_inside;
    }
}

递归解法：要注意对称判断，即左节点的左子节点和右节点的右子节点是否相等（外侧），以及左节点的右子节点和右节点的左子节点是否相等（内侧）。

【100】相同的树✔

题目链接：100. 相同的树 - 力扣（LeetCode）

题解：

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null) {
            return false;
        }
        if(p != null && q == null) {
            return false;
        }
        if(p == null && q == null) {
            return true;
        }
        if(p.val != q.val) {
            return false;
        }
        // else：p和q节点相同，继续判断其子节点
        else {
            boolean compare_left = isSameTree(p.left, q.left);
            boolean compare_right = isSameTree(p.right, q.right);
            return compare_left && compare_right;
        }
    }
}

递归判断左右节点。

【572】另一颗树的子树✔

题目链接：572. 另一棵树的子树 - 力扣（LeetCode）

题解：

class Solution {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        boolean compare_cur = judge(root, subRoot);  // 判断以root为根节点的树是否包含subRoot子树
        boolean compare_left = false;
        boolean compare_right = false;
        if(root.left != null) {
            compare_left = isSubtree(root.left, subRoot);  // 递归判断以root.left为根节点的树是否包含subRoot子树
        }
        if(root.right != null) {
            compare_right = isSubtree(root.right, subRoot);  // 递归判断以root.right为根节点的树是否包含subRoot子树
        }
        return compare_cur || compare_left || compare_right;  // 返回结果
    }

    // judge函数用于判断 以root为根节点的树 和 以subRoot为根节点的树 是否相同
    public boolean judge(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot != null) {
            return false;
        }
        if(root != null && subRoot == null) {
            return false;
        }
        if(root == null && subRoot == null) {
            return true;
        }
        if(root.val != subRoot.val) {
            return false;
        }
        // else：root和subRoot节点相同，继续判断其子节点
        else {
            boolean compare_left = judge(root.left, subRoot.left);
            boolean compare_right = judge(root.right, subRoot.right);
            return compare_left && compare_right;
        }
    } 
}

利用100. 相同的树 - 力扣（LeetCode）的解题方法判断两棵树是否是同一棵树，主函数递归判断以root为根节点的树是否包含subRoot子树。

【222】完全二叉树的节点个数✔

题目链接：222. 完全二叉树的节点个数 - 力扣（LeetCode）

题解（BFS）：

class Solution {
    public int countNodes(TreeNode root) {
        int number = 0;
        if(root == null) {
            return number;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int count = queue.size();
            while(count > 0) {
                TreeNode node = queue.poll();
                number++;  // 每弹出一个节点，计数加一
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
                count--;
            }
        }
        return number;
    }
}

整体思路同基础的层序遍历一样。

题解（DFS）：

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return countNodes(root.left) + countNodes(root.right) + 1;
    }
}

递归实现DFS

【110】平衡二叉树✔

题目链接：110. 平衡二叉树 - 力扣（LeetCode）

题解：

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        int left_depth = depth(root.left);  // 计算左子树深度
        int right_depth = depth(root.right);  // 计算右子树深度
        // 如果左子树深度与右子树深度的差值小于等于1，则继续判断左子树和右子树是否为平衡二叉树
        if(Math.abs(left_depth - right_depth) <= 1) {
            boolean judge_left = isBalanced(root.left);
            boolean judge_right = isBalanced(root.right);
            return judge_left && judge_right;
        }
        // 如果左子树深度与右子树深度的差值大于1，直接返回false
        return false;
    }
    // 用于计算以root为根节点的树的深度
    public int depth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

编写递归函数用于计算二叉树的深度，然后递归判断左右子树是否为平衡二叉树。

【257】二叉树的所有路径✔❗

题目链接：257. 二叉树的所有路径 - 力扣（LeetCode）

题解：

class Solution {
    List<String> result = new ArrayList<>();  // 用于存储最终的结果
    List<String> path = new ArrayList<>();  // 用于临时存储单一路径

    public List<String> binaryTreePaths(TreeNode root) {
        findPath(root);
        return result;
    }

    public void findPath(TreeNode root) {
        path.add(root.val + "");  // 添加当前节点到path路径
        // 如果到达叶子节点
        if(root.left == null && root.right == null) {
            String res = String.join("->", path);
            result.add(res);  // 将完整路径path添加到最终结果
            return;
        }
        if(root.left != null) {
            findPath(root.left);  // 递归添加当前节点的左节点
            path.remove(path.size() - 1);  // 回溯
        }
        if(root.right != null) {
            findPath(root.right);  // 递归添加当前节点的右节点
            path.remove(path.size() - 1);  // 回溯
        }
    }
}

使用回溯法。

注意❗：

• 指定连接符将字符串集合的元素拼接为一个完整的字符串：String res = String.join("->", path);

【404】左叶子之和

题目链接：404. 左叶子之和 - 力扣（LeetCode）

题解：

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int left_sum = sumOfLeftLeaves(root.left);  // 递归计算左子树
        int right_sum = sumOfLeftLeaves(root.right);  // 递归计算右子树
        int value = 0;
        // 如果当前节点的左节点为叶子节点，则记录其值
        if(root.left != null && root.left.left == null && root.left.right == null) {
            value = root.left.val;
        }
        return left_sum + right_sum + value;  // 返回总和
    }
}

递归需采用后序遍历，因为结果需要逐层向上传递。

【513】找树左下角的值✔

题目链接：513. 找树左下角的值 - 力扣（LeetCode）

题解（BFS）：

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int result = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode node = queue.poll();
            // 每一层遍历先添加右侧节点
            if(node.right != null) {
                queue.add(node.right);
            }
            // 后添加左侧节点
            if(node.left != null) {
                queue.add(node.left);
            }
            // 每层最后访问的节点就是最左边的节点
            result = node.val;
        }
        return result;
    }
}

整体思路同基础的层序遍历一样，但是在遍历每一层的时候先将右子节点添加至队列，再添加左子节点到队列。

【112】路径总和❗

题目链接：112. 路径总和 - 力扣（LeetCode）

题解（DFS）：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) {
            return false;
        }
        // 判断到叶子节点，返回结果
        if(root.left == null && root.right == null) {
            return root.val == targetSum ? true : false;
        }
        boolean left_result = false;
        boolean right_result = false;
        if(root.left != null) {
            left_result = hasPathSum(root.left, targetSum - root.val);
            // targetSum += root.val;  // 注意本题一定不是回溯！
        }
        if(root.right != null) {
            right_result = hasPathSum(root.right, targetSum - root.val);
            // targetSum += root.val;  // 注意本题一定不是回溯！
        }
        return left_result || right_result;
    }
}

注意❗：本题一定不是回溯。DFS遍历到叶子节点直接将结果返回。

【113】路径总和Ⅱ✔❗

题目链接：113. 路径总和 II - 力扣（LeetCode）

题解：

class Solution {
    List<List<Integer>> result = new ArrayList<>();  // 用于存储最终的结果
    List<Integer> path = new ArrayList<>();  // 用于临时存储单一路径

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if(root == null) {  // 做空判断
            return result;
        }
        findPath(root, targetSum);
        return result;
    }

    public void findPath(TreeNode root, int targetSum) {
        path.add(root.val);  // 添加当前节点到path路径
        // 如果到达叶子节点并且路径总和符合条件，则将该路径添加至result中
        if(root.left == null && root.right == null  && root.val == targetSum) {
            result.add(new ArrayList<>(path));   // 注意：必须新建路径对象，不可直接添加path！
            return;
        }
        if(root.left != null) {
            findPath(root.left, targetSum - root.val);  // 递归添加当前节点的左节点
            path.remove(path.size() - 1);  // 回溯
        }
        if(root.right != null) {
            findPath(root.right, targetSum - root.val);  // 递归添加当前节点的右节点
            path.remove(path.size() - 1);  // 回溯
        }
    }
}

使用回溯法。

注意❗：在收获结果时必须新建一个路径对象，否则传递的path为引用。

【106】从中序与后序遍历序列构造二叉树✔❗

题目链接：106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0 || postorder.length == 0) {
            return null;
        }
        int root_value = postorder[postorder.length - 1];  // 当前节点在后序遍历数组的最后一个
        TreeNode root = new TreeNode(root_value);  // 创建当前节点

        int index = 0;  // 作用：标记右中序的起始位置，左后序的结束位置，右后序的起始位置

        // 左中序
        List<Integer> left_inorder = new ArrayList<>();
        for(int i = 0; i < inorder.length; i++) {
            if(inorder[i] == root_value) {
                index = i;
                break;
            }
            left_inorder.add(inorder[i]);
        }
        int[] LEFT_inorder = left_inorder.stream().mapToInt(Integer::intValue).toArray();  // 利用stream()流将List<Integer>集合转化为int[]数组

        // 右中序
        List<Integer> right_inorder = new ArrayList<>();
        for(int i = index + 1; i < inorder.length; i++) {
            right_inorder.add(inorder[i]);
        }
        int[] RIGHT_inorder = right_inorder.stream().mapToInt(Integer::intValue).toArray();  // 利用stream()流将List<Integer>集合转化为int[]数组

        // 左后序
        List<Integer> left_postorder = new ArrayList<>();
        for(int i = 0; i < index; i++) {
            left_postorder.add(postorder[i]);
        }
        int[] LEFT_postorder = left_postorder.stream().mapToInt(Integer::intValue).toArray();  // 利用stream()流将List<Integer>集合转化为int[]数组

        // 右后序
        List<Integer> right_postorder = new ArrayList<>();
        for(int i = index; i < postorder.length - 1; i++) {
            right_postorder.add(postorder[i]);
        }
        int[] RIGHT_postorder = right_postorder.stream().mapToInt(Integer::intValue).toArray();  // 利用stream()流将List<Integer>集合转化为int[]数组

        root.left = buildTree(LEFT_inorder, LEFT_postorder);  // 递归连接左子树
        root.right = buildTree(RIGHT_inorder, RIGHT_postorder);  // 递归连接右子树

        return root;
    }
}

注意index的记录。

记忆❗：

• 利用stream()流将List<Integer> 集合转化为int[]数组：int[] LEFT_inorder = left_inorder.stream().mapToInt(Integer::intValue).toArray();

【105】从前序与中序遍历序列构造二叉树✔

题目链接：105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0 || inorder.length == 0) {
            return null;
        }

        int root_val = preorder[0];  // 当前节点在前序遍历数组的第一个
        TreeNode root = new TreeNode(root_val);  // 创建当前节点

        int index = 0;
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == root_val) {
                index = i;
                break;
            }
        }

        //左前序
        List<Integer> left_preorder = new ArrayList<>();  
        for (int i = 1; i <= index; i++) {
            left_preorder.add(preorder[i]);
        }
        int[] LEFT_preorder = left_preorder.stream().mapToInt(Integer::intValue).toArray();

        //右前序
        List<Integer> right_preorder = new ArrayList<>();  
        for (int i = index + 1; i < preorder.length; i++) {
            right_preorder.add(preorder[i]);
        }
        int[] RIGHT_preorder = right_preorder.stream().mapToInt(Integer::intValue).toArray();

        //左中序
        List<Integer> left_inorder = new ArrayList<>();  
        for (int i = 0; i < index; i++) {
            left_inorder.add(inorder[i]);
        }
        int[] LEFT_inorder = left_inorder.stream().mapToInt(Integer::intValue).toArray();

        //右中序
        List<Integer> right_inorder = new ArrayList<>();  
        for (int i = index + 1; i < inorder.length; i++) {
            right_inorder.add(inorder[i]);
        }
        int[] RIGHT_inorder = right_inorder.stream().mapToInt(Integer::intValue).toArray();

        root.left = buildTree(LEFT_preorder, LEFT_inorder);
        root.right = buildTree(RIGHT_preorder, RIGHT_inorder);

        return root;
    }
}

注意index的记录。

【654】最大二叉树✔

题目链接：654. 最大二叉树 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums.length == 0) {
            return null;
        }
		
        // 找到当前数组中的最大值为该节点的值
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++) {
            max = max < nums[i] ? nums[i] : max;
        }
		
        TreeNode root = new TreeNode(max);  // 创建当前节点
        int index = 0;  // 作用：标记左子树的数组的结束位置，右子树的数组的起始位置
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == max) {
                index = i;
                break;
            }
        }

        // 左子树的数组
        List<Integer> left_nums = new ArrayList<>();
        for(int i = 0; i < index; i++) {
            left_nums.add(nums[i]);
        }
        int[] LEFT_nums = left_nums.stream().mapToInt(Integer::intValue).toArray();

        // 右子树的数组
        List<Integer> right_nums = new ArrayList<>();
        for(int i = index + 1; i < nums.length; i++) {
            right_nums.add(nums[i]);
        }
        int[] RIGHT_nums = right_nums.stream().mapToInt(Integer::intValue).toArray();

        root.left = constructMaximumBinaryTree(LEFT_nums);
        root.right = constructMaximumBinaryTree(RIGHT_nums);

        return root;
    }
}

注意index的记录。

【617】合并二叉树✔

题目链接：617. 合并二叉树 - 力扣（LeetCode）

题解：

class Solution {
    // 递归
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) return root2;
        if (root2 == null) return root1;

        // 如果两个节点都不为空，以root1为“根”进行操作
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left,root2.left);
        root1.right = mergeTrees(root1.right,root2.right);
        return root1;  // 最后返回root1
    }
}

以root1为主要的“根”进行操作。

【700】二叉搜索树中的搜索✔

题目链接：700. 二叉搜索树中的搜索 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        // 如果当前值小于val，递归查找左子树；如果当前值大于val，递归查找右子树
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}

如果当前值小于val，递归查找左子树；如果当前值大于val，递归查找右子树。

【98】验证二叉搜索树❗

题目链接：98. 验证二叉搜索树 - 力扣（LeetCode）

题解：

class Solution {
    TreeNode max;  // max表示当前节点的前一个节点
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        // 判断左子树
        boolean left_judge = isValidBST(root.left);
        // 判断中间节点（如果当前节点小于等于前一个节点的值，返回false）
        if(max != null && root.val <= max.val) {
            return false;
        }
        max = root; // 将当前节点赋值给max
        // 判断右节点
        boolean right_judge = isValidBST(root.right);
        return left_judge && right_judge;
    }
}

关键❗：二叉搜索树的中序遍历是非严格递增的，所以采用中序遍历。

思路：需要有一个额外的节点记录当前节点的前一个节点。首先递归判断左子树，然后判断当前节点是否大于前一个节点的值，最后递归遍历右子树。

【530】二叉搜索树的最小绝对差✔

题目链接：530. 二叉搜索树的最小绝对差 - 力扣（LeetCode）

题解：

class Solution {
    int min = Integer.MAX_VALUE;  // 记录最小差值
    TreeNode pre_node;  // pre_node表示当前节点的前一个节点
    public int getMinimumDifference(TreeNode root) {
        // 如果遇到null，返回最大值
        if(root == null) {
            return Integer.MAX_VALUE;
        }
        getMinimumDifference(root.left);  // 递归遍历左子树
        // 判断中间节点，更新最小差值
        if(pre_node != null) {
            min = min < (root.val - pre_node.val) ? min : (root.val - pre_node.val);
        }
        pre_node = root;  // 将当前节点赋值给pre_node
        getMinimumDifference(root.right);  // 递归遍历右子树
        return min;
    }
}

使用中序遍历。去不断地更新差值。

【501】二叉搜索树中的众数✔❗

题目链接：501. 二叉搜索树中的众数 - 力扣（LeetCode）

题解：

class Solution {
    List<Integer> result = new ArrayList<>();  // 用于记录结果
    int maxCount = 0;  // 用于记录元素的最高出现频率
    int count = 0;  // 用于更新记录当前元素出现的频率
    TreeNode pre_node;  // 表示当前节点的前一个节点

    public int[] findMode(TreeNode root) {
        inorder(root);
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    public void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);  // 递归遍历左子树

        // 判断中间节点
        // 如果当前节点为空（初始化前）或者当前节点的值跟前一个节点的值不同（表示遇到了新的值）
        if (pre_node == null || root.val != pre_node.val) {
            count = 1;  // 更新count为1
        } 
        // 否则表示当前节点的值还没结束
        else {
            count++;  // 更新计数
        }
        // 如果当前元素出现的频率大于上一个元素出现的频率
        if (count > maxCount) {
            result.clear();  // 首先清空结果集合
            result.add(root.val);  // 将当前的元素添加到结果集合中
            maxCount = count;  // 更新maxCount
        } 
        // 如果当前元素出现的频率等于上一个元素出现的频率
        else if (count == maxCount) {
            result.add(root.val);  // 将当前的元素添加到结果集合中
        }

        pre_node = root;  // 将当前节点赋值给pre_node
        inorder(root.right);  // 递归遍历右子树
    }
}

使用中序遍历。

注意❗：

• 清空集合：result.clear();

【236】二叉树的最近公共祖先

题目链接：236. 二叉树的最近公共祖先 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果root为空，或者为p或q，则直接返回root
        if(root == null || root == p || root == q) {
            return root;
        }

        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果左右节点都不为空，说明该节点就是公共祖先，直接返回该节点
        if(left != null && right != null) {
            return root;
        } 
        // 如果左节点不为空，则说明左节点是p或q的祖先，返回左节点（逐层向上返回的关键）
        else if(left != null && right == null) {
            return left;
        } 
        // 如果右节点不为空，则说明右节点是p或q的祖先，返回右节点（逐层向上返回的关键）
        else if(left == null && right != null) {
            return right;
        } 
        // 如果左右节点都为空，直接返回null
        else {
            return null;
        }
    }
}

后序遍历，递归返回公共祖先。注意向上传递结果的关键是返回左或右节点。

【235】二叉搜索树的最近公共祖先✔

题目链接：235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果root为空，或者为p或q，则直接返回root
        if(root == null || root == p || root == q) {
            return root;
        }

        // 后序遍历
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 如果左右节点都不为空，说明该节点就是公共祖先，直接返回该节点
        if(left != null && right != null) {
            return root;
        } 
        // 如果左节点不为空，则说明左节点是p或q的祖先，返回左节点（逐层向上返回的关键）
        else if(left != null && right == null) {
            return left;
        } 
        // 如果右节点不为空，则说明右节点是p或q的祖先，返回右节点（逐层向上返回的关键）
        else if(left == null && right != null) {
            return right;
        } 
        // 如果左右节点都为空，直接返回null
        else {
            return null;
        }
    }
}

同236. 二叉树的最近公共祖先 - 力扣（LeetCode）解法一样。

【701】二叉搜索树中的插入操作

题目链接：701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 该方法的策略是将要插入的节点链接到叶子节点上
        // 如果遇到了空节点，就说明该插入了，就返回要插入的新节点
        if (root == null) {
            TreeNode rootNode = new TreeNode(val);
            return rootNode;
        }
        // 如果要插入的值大于当前节点值，则递归遍历右子树
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        // 如果要插入的值小于当前节点值，则递归遍历左子树
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }
        return root;  // 最终返回插值后的新的树
    }
}

该方法的策略是将要插入的节点链接到叶子节点上。所以根据二叉搜索树的条件递归遍历左右子树，一旦遇到叶子节点就插入。

【450】删除二叉搜索树中的节点

题目链接：450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        // 如果root为null，直接返回
        if (root == null) {
            return root;
        }
        // 如果待删除节点为叶子节点，则直接返回null（表示删去）
        if (root.val == key && root.left == null && root.right == null) {
            return null;
        }
        // 如果待删除节点的左节点不为空，右节点为空，则直接返回左节点
        if (root.val == key && root.left != null && root.right == null) {
            return root.left;
        }
        // 如果待删除节点的右节点不为空，左节点为空，则直接返回右节点
        if (root.val == key && root.left == null && root.right != null) {
            return root.right;
        }
        // 如果待删除节点的左、右节点都不为空，本方法的策略如下：
        // 直接返回右节点，而左子树则挂到右子树的最底最左的叶子节点的下方。（二叉搜索树的特性）
        if (root.val == key && root.left != null && root.right != null) {
            TreeNode cur = root.right;  // 定义一个指针指向右节点
            while (cur.left != null) {
                cur = cur.left;  // 通过循环将指针指向右子树的最底最左的叶子节点
            }
            cur.left = root.left;  // 将左子树链接到叶子节点上
            return root.right;  // 返回右节点
        }

        // 如果要删除的值小于当前节点值，则递归遍历左子树
        if (key < root.val) {
            root.left = deleteNode(root.left, key);
        }
        // 如果要删除的值大于当前节点值，则递归遍历右子树
        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        }
        
        return root;  // 返回删除节点后的新的二叉搜索树
    }
}

如果待删除节点的左、右节点都不为空的删除策略：直接返回右节点，而左子树则挂到右子树的最底最左的叶子节点的下方。（二叉搜索树的特性）

【669】修建二叉搜索树✔

题目链接：669. 修剪二叉搜索树 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        // root在[low,high]范围外
        // 递归逐步删除小于low的叶子节点
        if (root.val < low) {
            return trimBST(root.right, low, high);
        }
        // 递归逐步删除大于high的叶子节点
        if (root.val > high) {
            return trimBST(root.left, low, high);
        }
        // root在[low,high]范围内，接收新的左右节点
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

思路，通过递归逐步删除[low,high]范围外的叶子节点。

【108】将有序数组转化为二叉搜索树✔

题目链接：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

题解：

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0) {
            return null;
        }
        int index = nums.length / 2;  // 找到nums中间的数
        TreeNode root = new TreeNode(nums[index]);  // 根节点在数组中间

        // 构建左子树的数组
        List<Integer> left_nums = new ArrayList<>();
        for(int i = 0; i < index; i++) {
            left_nums.add(nums[i]);
        }
        int[] LEFT_nums = left_nums.stream().mapToInt(Integer::intValue).toArray();

        // 构建右子树的数组
        List<Integer> right_nums = new ArrayList<>();
        for(int i = index + 1; i < nums.length; i++) {
            right_nums.add(nums[i]);
        }
        int[] RIGHT_nums = right_nums.stream().mapToInt(Integer::intValue).toArray();

        root.left = sortedArrayToBST(LEFT_nums);  // 递归构建左子树
        root.right = sortedArrayToBST(RIGHT_nums);  // 递归构建右子树

        return root;
    }
}

思路，将有序数组构建为二叉搜索树，树的根节点在有序数组的中间，找到根节点再分别定义左右子树的有序数组，然后递归构建左右子树。

【538】把二叉搜索树转换为累加树✔

题目链接：538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

题解：

class Solution {
    TreeNode pre = new TreeNode(0);  // 定义当前节点的前一个节点，初始值为0
    
    public TreeNode convertBST(TreeNode root) {
        if(root == null) {
            return null;
        }
        // 按照右中左的顺序遍历
        convertBST(root.right);  // 遍历右节点
        root.val = root.val + pre.val;  // 当前节点的值等于当前节点的值加前一个节点的值
        pre = root;  // 更新pre为当前节点
        convertBST(root.left);  // 遍历左节点
        return root;
    }
}

思路：更新完的累加树按照右中左的顺序遍历其实也是递增的。考虑用一个指针记录前一个节点的值，并不断迭代进行更新。

回溯算法

贪心算法

动态规划

单调栈

图论

---

后记

To be continued…