数据结构与算法

一、数据结构

线性结构：数组、队列、链表、栈

• 顺序存储（地址连续）
• 链式存储（地址不一定连续）

非线性结构：二维数组、多维数组、广义表、树、图

---

①数组

❶稀疏数组

稀疏数组是一种用来压缩数据量的数据结构，简而言之，就是记录特殊值，然后剩下大量重复的数据可以消减。

例如下方是一个普通二维数组

0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 2 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

这么一个二维数组，化成稀疏数组可以表示为：

   行 列 值
0  6  6  2
1  1  2  1
2  2  3  2

1. 稀疏数组第一行表示原数组有多少行，多少列，有多少个非零元素（有效值）
2. 稀疏数组是从0开始的
3. 稀疏数组的行数等于有效值+1，列数固定都为3

二维数组转稀疏数组的步骤：

• 遍历二维数组，得到有效值个数 sum
• 根据 sum 创建稀疏数组 sparseArr = int [sum+1][3]
• 将有效值存入稀疏数组

还原稀疏数组步骤：

• 创建一个新的数组，其行和列等于稀疏数组首行数据

• 遍历稀疏数组，将对应数值赋值给新的数组

• 最后可以验证一下原始的数组和还原后的数组是否相等

//稀疏数组：用来减少数据量
public class SparseArray {
    public static void main(String[] args) {
        // 一、构建原始数组
        // 创建一个二维数组6*6  0：没有棋子，1：黑棋  2：白棋
        int[][] chessArr = new int[6][6];
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        System.out.println("原始数组:");
        for (int[] row : chessArr) {
            for (int data : row) {
                System.out.print(data+"\t");
            }
            System.out.println();
        }
        System.out.println("====================");

        // 二、转换成稀疏数组
        int sum = 0;
        //1.先遍历二维数组，获取有效值的个数
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[0].length; j++) {
                if(chessArr[i][j] != 0) {
                    sum++;//有效值的个数
                }
            }
        }
        //2.创建对应稀疏数组
        int [][]sparseArr = new int[sum+1][3];
        //第一行赋值
        sparseArr[0][0] = chessArr.length;
        sparseArr[0][1] = chessArr[0].length;
        sparseArr[0][2] = sum;
        //3.遍历初始的二维数组，将非零的值，存放到稀疏数组中
        int count = 0;
        for (int i = 0; i < chessArr.length; i++) {
            for (int j = 0; j < chessArr[0].length; j++) {
                if (chessArr[i][j] != 0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
        //4.输出稀疏数组
        System.out.println("稀疏数组:");
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.println(sparseArr[i][0]+"\t"+sparseArr[i][1]+"\t"+sparseArr[i][2]+"\t");
        }

        // 三、还原数组
        int [][] ChessArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            ChessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        System.out.println("=======================");
        //打印还原的数组
        System.out.println("输出还原后的数组：");
        for (int[] row : ChessArr2) {
            for (int data : row) {
                System.out.print(data+"\t");
            }
            System.out.println();
        }


        //四、验证两个数组是否相等，可用Arrays工具类
        int flag = 0;
        for (int i = 0; i < chessArr.length; i++) {
            if (!Arrays.equals(chessArr[i],ChessArr2[i])){
                flag++;
            }
        }
        if (flag==0){
            System.out.println("初始数组和还原后的数组相等");
        }
    }
}

❷数组模拟队列

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图

maxSize 是该队列的最大容量，两个变量 front 及 rear 分别记录队列前后端的下标

class ArrayQueue {
    private int MaxSize;  // 队列大小
    private int front;   // 队列头
    private int rear;   // 队列尾
    private int[] arr; // 数组存放数据

    // 一、创建队列的构造器
    public ArrayQueue(int MaxSize) {
        this.MaxSize = MaxSize;
        arr = new int[this.MaxSize];
        front = -1;
        rear = -1;
    }

    //二、判断队列是否满
    public boolean isFull() {
        return rear == MaxSize - 1;
    }

    //三、判断队列是否空
    public boolean isEmpty() {
        return rear == front;
    }

    //四、入队
    public void addQueue(int num) {
        if (isFull()) {
            System.out.println("队列已满，无法在进行入队操作");
            return;
        }
        arr[++rear] = num;
    }

    //五、出队
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法出队");
        }
        return arr[++front];
    }

    //六、显示队列数据
    public void showQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，无法遍历");
        }
        for (int i = front+1; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }

    //七、显示队列头数据
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有数据");
        }
        return arr[front + 1];
    }

}

测试

public class ArrayQueueDemo {
    public static void main(String[] args) {
        // 构造队列
        ArrayQueue queue = new ArrayQueue(5);
        // 入队
        queue.addQueue(1);
        queue.addQueue(2);
        queue.addQueue(3);
        queue.addQueue(4);
        queue.addQueue(5);
        // 出队
        System.out.println(queue.getQueue());
        // 遍历队列
        queue.showQueue();
        // 队首
        System.out.println(queue.headQueue());

    }
}

❸LeetCode真题

二分法：704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] 大于nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);// 防止溢出 等同于(left + right)/2
            if(nums[mid] == target){
                return mid;
            }
            else if(nums[mid] < target){
                left = mid + 1;
            }else{
                right = mid -1;
            }
        }
        return -1;
    }
}

双指针：27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

class Solution {
    public int removeElement(int[] nums, int val) {
        //快慢指针解法
        int slow = 0; //慢指针
        //快指针，无论与val值是否相同每遍历一次都要移动一位
        for(int fast = 0; fast < nums.length; fast++){
            //快指针先走，判断快指针指向的元素是否等于val
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;  //只有当快指针不等于val的时候，慢指针才和快指针一起移动一位
            }
        }
        return slow;
    }
}

class Solution {
    public int removeElement(int[] nums, int val) {
        int idx = 0;
        for (int x : nums) {
            if (x != val) nums[idx++] = x;
        }
        return idx;
    }
}

双指针：977. 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

//时间复杂度是 O(n + nlogn)
class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i = 0 ; i < nums.length; i++){
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

//时间复杂度为 O(n)
class Solution {
    public int[] sortedSquares(int[] nums) {
        int[] res = new int[nums.length];
        int i = 0, j = nums.length - 1, k = nums.length - 1;
        while(i <= j){
            if(nums[i]*nums[i] > nums[j] * nums[j]){
                res[k--] =  nums[i] * nums[i];
                i++;
            }
            else{
                res[k--] =  nums[j] * nums[j];
                j--;
            }
        }
        return res;
    }
}

滑动窗口：209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [nums<sub>l</sub>, nums<sub>l+1</sub>, ..., nums<sub>r-1</sub>, nums<sub>r</sub>] ，并返回其长度。如果不存在符合条件的子数组，返回 0

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

//时间复杂度 O(n^2)
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int sum = 0;
        int sumLen = 0;
        for(int i = 0 ; i < nums.length; i++){
            sum = 0;
            for(int j = i; j < nums.length; j++){
                sum += nums[j];
                if(sum >= target){
                    sumLen = j - i + 1;
                    res = res > sumLen ? sumLen : res;
                    break;
                }
            } 
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }
}

//时间复杂度 O(n)
class Solution {
    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}

模拟法： 59. 螺旋矩阵 II

给你一个正整数 n ，生成一个包含 1 到 n<sup>2</sup> 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

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

示例 2：

输入：n = 1
输出：[[1]]

思路：

• 生成一个 n×n 空矩阵 res，随后模拟整个向内环绕的填入过程：
  • 定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 end = n * n；
  • 当 num <= end 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后：
    • 执行 num += 1：得到下一个需要填入的数字；
    • 更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 1。
  • 使用num <= end而不是l < r || t < b作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。
• 最终返回 res 即可。

class Solution {
    public int[][] generateMatrix(int n) {
        int l = 0, r = n - 1, t = 0, b = n - 1;
        int[][] res = new int[n][n];
        int num = 1, end = n * n;
        while(num <= end){
            for(int i = l; i <= r; i++) res[t][i] = num++; // left to right.
            t++;
            for(int i = t; i <= b; i++) res[i][r] = num++; // top to bottom.
            r--;
            for(int i = r; i >= l; i--) res[b][i] = num++; // right to left.
            b--;
            for(int i = b; i >= t; i--) res[i][l] = num++; // bottom to top.
            l++;
        }
        return res;
    }
}

模拟法：915. 分割数组

给定一个数组 nums ，将其划分为两个连续子数组 left 和 right， 使得：

• left 中的每个元素都小于或等于 right 中的每个元素。
• left 和 right 都是非空的。
• left 的长度要尽可能小。

在完成这样的分组后返回 left 的 长度。

用例可以保证存在这样的划分方法。

示例 1：

输入：nums = [5,0,3,8,6]
输出：3
解释：left = [5,0,3]，right = [8,6]

示例 2：

输入：nums = [1,1,1,0,6,12]
输出：4
解释：left = [1,1,1,0]，right = [6,12]

两次遍历：O(n)

• 先通过一次遍历（从后往前）统计出所有后缀的最小值 minRight（使用数组进行维护）

• 然后再通过第二次遍历（从前往后）统计每个前缀的最大值 maxLeft（使用单变量进行维护）

• 第一个满足 maxLeft ≤ minRight[i + 1] 的 i 即为答案，此时 left 的长度为 i+1，因此答案需返回 i+1。

class Solution {
    public int partitionDisjoint(int[] nums) {
        int[] minRight = new int[nums.length];
        minRight[nums.length - 1] = nums[nums.length - 1];
        for(int i = nums.length - 2; i >= 0; i--){
            minRight[i] = Math.min(nums[i], minRight[i + 1]);
        }
        int maxLeft = 0;
        for(int i = 0; i < nums.length - 1; i++){
            maxLeft = Math.max(maxLeft, nums[i]);
            if(maxLeft <= minRight[i + 1]){
                return i + 1;
            }
        }
        return 0;
    }
}

哈希表：1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

进阶：你可以想出一个时间复杂度小于 O(n²) 的算法吗？

//暴力法O(n^2)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                if(nums[i] + nums[j] == target){
                    return new int[]{i,j};
                }
            }
        }
        return new int[0];
    }
}
//哈希表O(n)
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }
}

②链表

❶单向链表

特点

• 链表是以节点的方式来存储，是链式存储
• 每个节点包含 data 域 （存储数据），next 域（指向下一个节点）
• 链表的各个节点不一定是连续存储的
• 链表分带头节点的链表和没有头节点的链表，根据实际的需求来确定

/**
 * 定义节点
 */
class StudentNode {
    int id;
    String name;
    StudentNode next;

    public StudentNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "StudentNode{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }
}

/**
 * 创建链表
 */
class singleLinkedList {
    //头节点，防止被修改，设置为私有的
    private StudentNode head = new StudentNode(0, "");

    //插入节点
    public void addNode(StudentNode node) {
        //因为头节点不能被修改，所以创建一个辅助节点
        StudentNode temp = head;
        //找到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    //按id顺序插入节点
    public void addByOrder(StudentNode node) {
        //如果没有首节点，就直接插入
        if (head.next == null) {
            head.next = node;
            return;
        }
        //辅助节点，用于找到插入位置和插入操作
        StudentNode temp = head;
        //节点的下一个节点存在，且它的id小于要插入节点的id，就继续下移
        while (temp.next != null && temp.next.id < node.id) {
            temp = temp.next;
        }
        //如果temp的下一个节点存在，则执行该操作
        //且插入操作，顺序不能换
        if (temp.next != null) {
            node.next = temp.next;
        }
        temp.next = node;
    }

    //遍历链表
    public void traverseNode() {
        if (head.next == null) {
            System.out.println("链表为空");
        }
        StudentNode temp = head;
        while (temp.next != null) {
            System.out.println(temp.next);
            temp = temp.next;
        }
    }

    //根据id来修改节点信息
    public void changeNode(StudentNode node) {
        if (head == null) {
            System.out.println("链表为空，请先加入该学生信息");
            return;
        }
        StudentNode temp = head;
        //遍历链表，找到要修改的节点
        while (temp.next != null && temp.id != node.id) {
            temp = temp.next;
        }
        //如果temp已经是最后一个节点，判断id是否相等
        if (temp.id != node.id) {
            System.out.println("未找到该学生的信息，请先创建该学生的信息");
            return;
        }
        //修改信息
        temp.name = node.name;
    }

    //删除节点
    public void deleteNode(StudentNode node) {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        StudentNode temp = head;
        //遍历链表，找到要删除的节点
        while (temp.next != null && temp.next.id != node.id) {
            temp = temp.next;
        }
        if(temp.next == null){
            System.out.println("要删除的节点不存在");
            return;
        }
        //删除该节点
        temp.next = temp.next.next;

    }

    //得到第index个的节点
    public StudentNode getNodeByIndex(int index) {
        if (head.next == null) {
            System.out.println("链表为空!");
        }
        StudentNode temp = head;
        int length = 0;
        while (temp.next != null) {
            temp = temp.next;
            length++;
        }
        if (index > length) {
            throw new RuntimeException("链表越界");
        }

        temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //逆序遍历
    public void reverseTraverse() {
        if (head == null) {
            System.out.println("链表为空");
        }
        StudentNode temp = head;
        //创建栈，用于存放遍历到的节点
        Stack<StudentNode> stack = new Stack<>();
        while (temp.next != null) {
            stack.push(temp.next);
            temp = temp.next;
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}  
  
  
 public class SingleLinkedListDemo {
    public static void main(String[] args) {

        singleLinkedList linkedList = new singleLinkedList();

        //创建学生节点，并插入链表
        System.out.println("插入节点1和3：");
        StudentNode student1 = new StudentNode(1, "Jack");
        StudentNode student3 = new StudentNode(3, "Tom");
        linkedList.addNode(student1);
        linkedList.addNode(student3);
        linkedList.traverseNode();

        //按id大小插入
        System.out.println("有序插入节点2：");
        StudentNode student2 = new StudentNode(2, "Jerry");
        linkedList.addByOrder(student2);
        linkedList.traverseNode();

        //按id修改学生信息
        System.out.println("修改节点1信息：");
        student2 = new StudentNode(1, "Jack2");
        linkedList.changeNode(student2);
        linkedList.traverseNode();

        //获得第2个节点
        System.out.println("获得第2个节点：");
        System.out.println(linkedList.getNodeByIndex(2));

        //根据id删除学生信息
        System.out.println("删除学生信息：");
        student2 = new StudentNode(1, "Jack2");
        linkedList.deleteNode(student2);
        linkedList.traverseNode();
        
        //倒叙遍历链表
        System.out.println("倒序遍历链表：");
        linkedList.reverseTraverse();

    }
} 

链表为空

插入节点1和3：
StudentNode{id=1, name='Jack'}
StudentNode{id=3, name='Tom'}
有序插入节点2：
StudentNode{id=1, name='Jack'}
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
修改节点1信息：
StudentNode{id=1, name='Jack2'}
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
获得第2个节点：
StudentNode{id=2, name='Jerry'}
删除学生信息：
StudentNode{id=2, name='Jerry'}
StudentNode{id=3, name='Tom'}
倒序遍历链表：
StudentNode{id=3, name='Tom'}
StudentNode{id=2, name='Jerry'}

❷双向链表

class HeroNode {
    int id;
    String name;
    HeroNode next;
    HeroNode pre;

    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{id=" + id + ", name=" + name + "}";
    }
}


/**
 * 创建一个双向链表的类
 */
class DoubleLinkedList {

    //初始化一个头节点，头节点不动，不存放具体的数据
    HeroNode head = new HeroNode(0, "");
    //初始化一个尾节点，指向最后一个元素，默认等于head
    HeroNode tail = head;

    //遍历打印双向链表的方法
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //新增节点
    public void add(HeroNode heroNode) {
        tail.next = heroNode;
        heroNode.pre = tail;
        tail = heroNode;
    }

    //有序新增节点
    public void addByOrder(HeroNode heroNode) {
        HeroNode temp = head;
        // 标记添加的编号是否已经存在
        boolean flag = false;
        while (temp.next != null && temp.next.id <= heroNode.id) {
            if (temp.next.id == heroNode.id) {
                flag = true;
            }
            temp = temp.next;
        }
        // 判断flag
        if (flag) {
            System.out.printf("英雄编号【%d】已经存在了\n", heroNode.id);
        } else {
            // 插入到链表中
            // 1、将【heroNode的next】设置为【temp的next】
            heroNode.next = temp.next;
            // 判断是不是加在链表最后
            if (temp.next != null) {
                // 2、将【temp的next的pre】设为为【heroNode】
                temp.next.pre = heroNode;
            }
            // 3、将【temp的next】设置为【heroNode】
            temp.next = heroNode;
            // 4、将【heroNode的pre】设置为【temp】
            heroNode.pre = temp;
        }
    }

    //修改节点
    public void update(HeroNode heroNode) {
        // 判断是否为空
        if (head.next == null) {
            System.out.println("链表为空~~");
            return;
        }
        // 找到需要修改的节点
        HeroNode temp = head.next;
        // 表示是否找到这个节点
        boolean flag = false;
        while (temp != null) {
            if (temp.id == heroNode.id) {
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 根据flag判断是否找到要修改的节点
        if (flag) {
            temp.name = heroNode.name;
        } else { // 没有找到
            System.out.printf("没有找到编号为 %d 的节点，不能修改\n", heroNode.id);
        }
    }

    //删除节点
    public void delete(int id) {
        // 判断当前链表是否为空
        if (head.next == null) {
            System.out.println("链表为空，无法删除");
            return;
        }
        HeroNode temp = head;
        // 标志是否找到删除节点
        boolean flag = false;
        while (temp.next != null) {
            // 已经找到链表的最后
            if (temp.id == id) {
                // 找到待删除节点
                flag = true;
                break;
            }
            temp = temp.next;
        }
        // 判断flag，此时找到要删除的节点就是temp
        if (flag) {
            // 可以删除，将【temp的pre的next域】设置为【temp的next域】
            temp.pre.next = temp.next;
            // 如果是最后一个节点，就不需要指向下面这句话，否则会出现空指针 temp.next.pre = null.pre
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        }
    }

}


public class DoubleLinkedListDemo {
    public static void main(String[] args) {
        System.out.println("双向链表:");
        // 创建节点
        HeroNode her1 = new HeroNode(1, "宋江");
        HeroNode her2 = new HeroNode(2, "卢俊义");
        HeroNode her3 = new HeroNode(3, "吴用");
        HeroNode her4 = new HeroNode(4, "林冲");
        // 创建一个双向链表对象
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(her1);
        doubleLinkedList.add(her2);
        doubleLinkedList.add(her3);
        doubleLinkedList.add(her4);
        doubleLinkedList.list();

        // 修改
        HeroNode newHeroNode = new HeroNode(4, "公孙胜");
        doubleLinkedList.update(newHeroNode);
        System.out.println("修改节点4:");
        doubleLinkedList.list();

        // 删除
        doubleLinkedList.delete(3);
        System.out.println("删除节点3");
        doubleLinkedList.list();
        // 测试有序新增
        System.out.println("测试有序增加链表：");
        DoubleLinkedList doubleLinkedList1 = new DoubleLinkedList();
        doubleLinkedList1.addByOrder(her3);
        doubleLinkedList1.addByOrder(her2);
        doubleLinkedList1.addByOrder(her2);
        doubleLinkedList1.addByOrder(her4);
        doubleLinkedList1.addByOrder(her4);
        doubleLinkedList1.addByOrder(her2);
        doubleLinkedList1.addByOrder(her1);
        doubleLinkedList1.list();

    }
}

双向链表:
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=卢俊义}
HeroNode{id=3, name=吴用}
HeroNode{id=4, name=林冲}
修改节点4:
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=卢俊义}
HeroNode{id=3, name=吴用}
HeroNode{id=4, name=公孙胜}
删除节点3
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=卢俊义}
HeroNode{id=4, name=公孙胜}
测试有序增加链表：
英雄编号【2】已经存在了
英雄编号【4】已经存在了
英雄编号【2】已经存在了
HeroNode{id=1, name=宋江}
HeroNode{id=2, name=卢俊义}
HeroNode{id=3, name=吴用}
HeroNode{id=4, name=公孙胜}

❸循环链表

❹LeetCode真题

203. 移除链表元素

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

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

示例 2：

输入：head = [], val = 1
输出：[]

示例 3：

输入：head = [7,7,7,7], val = 7
输出：[]

/**
 * 添加虚节点方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */
public ListNode removeElements(ListNode head, int val) {
    if (head == null) {
        return head;
    }
    // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
    ListNode dummy = new ListNode(-1, head);
    ListNode pre = dummy;
    ListNode cur = head;
    while (cur != null) {
        if (cur.val == val) {
            pre.next = cur.next;
        } else {
            pre = cur;
        }
        cur = cur.next;
    }
    return dummy.next;
}



/**
 * 不添加虚拟节点and pre Node方式
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
       //去除开头节点
        while(head != null && head.val == val){
            head = head.next;
        }
        ListNode cur = head;
        while(cur != null){
            while(cur.next != null && cur.next.val == val){
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        return head;
    }
}

707. 设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

在链表类中实现这些功能：

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

示例：

MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
linkedList.get(1);            //返回2
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
linkedList.get(1);            //返回3

/**
* 单链表
*/
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}

class MyLinkedList {

    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }
    
    public int get(int index) {
        if(index < 0 || index >= size) return -1;
        ListNode cur = head;
        //包含一个虚拟头节点，所以查找第 index+1 个节点
        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) {
        if(index > size) return;
        if(index < 0) index = 0;
        ListNode pre = head;
        ListNode addNode = new ListNode(val);
        //找到要插入节点的前驱
        for(int i = 0; i < index; i++){
            pre = pre.next;
        }
        addNode.next = pre.next;
        pre.next = addNode;
        size++;
    }
    

    public void deleteAtIndex(int 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--;
    }
}


/**
*双链表
*/
class ListNode {
    int val;
    ListNode prev, next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}

class MyLinkedList {

    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head, tail;

    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        //这一步非常关键，否则在加入头结点的操作中会出现null.next的错误！！！
        head.next=tail;
        tail.prev=head;
    }
    
    public int get(int index) {
        //判断index是否有效
        if(index < 0 || index >= size) return -1;
        ListNode cur = head;
        //判断是哪一边遍历时间更短
        if(index > size / 2) {
            cur = tail;
            for(int i = size; i > index; i--){
                cur = cur.prev;
            }
        } else {
            //包含一个虚拟头节点，所以查找第 index+1 个节点
            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) {
        if(index > size) return;
        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.prev = newNode;
        newNode.prev = pre; 
        pre.next = newNode;
        size++;//节点数+1
    }
    

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        ListNode pre = head;
        //找到要删除节点的前驱
        for(int i = 0; i < index; i++){
            pre = pre.next;
        }
        pre.next.next.prev = pre;
        pre.next = pre.next.next;
        
        size--;
    }
}

206. 反转链表

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

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

//迭代法（双指针法）
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while(cur != null){
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

// 递归法
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
    public ListNode reverse(ListNode pre, ListNode cur){
        if (cur == null) {
            return pre;
        }
        ListNode tmp = null;
        tmp = cur.next;
        cur.next = pre;
        return reverse(cur,tmp);
    }
}

//栈实现1(不推荐，效率不高)
class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> stack = new ArrayDeque<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while(!stack.isEmpty()){
            temp.next = stack.pop();
            temp = temp.next;
        }
        temp.next = null; //最后节点不接null会形成环链
        return dummy.next;
    }
}
//栈实现2(不推荐，效率不高)
class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> stack = new ArrayDeque<>();
        while(head != null){
            stack.add(head);
            head = head.next;
        }
        ListNode dummy = new ListNode(0),
        ListNode temp = dummy;
        while(stack.size() != 0){
            temp.next = new ListNode(stack.pop());//防止形成环链
            temp = temp.next;
        }
        return dummy.next;
    }
}

24. 两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

输入：head = []
输出：[]

示例 3：

输入：head = [1]
输出：[1]

递归法：O(n)

• 1.返回值：交换完成的子链表
• 2.调换：设需要交换的两个点为 first 和 second，first 连接后面交换完成的子链表，second 连接 first
• 3.终止条件：head 为空指针或者 next 为空指针，也就是当前无节点或者只有一个节点，无法进行交换

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode first = head;
        ListNode second = head.next;
        first.next = swapPairs(second.next);
        second.next = first;
        return second;
    }
}

迭代法：O(n)

class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(0,head); //虚拟头节点
        ListNode temp = dummyHead;
        while (temp.next != null && temp.next.next != null) {
            ListNode node1 = temp.next;
            ListNode node2 = temp.next.next;
            temp.next = node2;         //步骤一
            node1.next = node2.next;  //步骤二
            node2.next = node1;             //步骤三
            temp = node1; //后移两位，准备下一轮交换
        }
        return dummyHead.next;
    }
}

19. 删除链表的倒数第 N 个结点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

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

暴力法：O(n)

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //计算链表长度
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            ++length;
            temp = temp.next;
        }
        //删除节点
        ListNode dummy = new ListNode(0, head);
        ListNode cur = dummy;
        for (int i = 0; i < length - n; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;
    }
}

双指针法：O(n)

由于我们需要找到倒数第 n 个节点，因此我们可以使用两个指针 first 和 second 同时对链表进行遍历，并且 first比 second超前 n 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。

具体地，初始时 first和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 n。此时 first 比 second 超前了 n 个节点。在这之后，同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾（即 first为空指针）时，second 恰好指向倒数第 n 个节点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

160. 相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。
在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。
在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。
由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
这两个链表不相交，因此返回 null 。

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ，做如下操作：

• 指针 A 先遍历完链表 headA ，再开始遍历链表 headB ，当走到 node 时，共走步数为：a+(b−c)
• 指针 B 先遍历完链表 headB ，再开始遍历链表 headA ，当走到 node 时，共走步数为：b+(a−c)

a+(b−c) = b+(a−c)，此时指针 A , B 重合 ，并有两种情况：

1. 若两链表 有 公共尾部 (即 c>0 ) ：指针 A , B 同时指向「第一个公共节点」node 。
2. 若两链表 无 公共尾部 (即 c=0) ：指针 A , B 同时指向 null 。

因此返回 A 即可。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while(A != B){
            if(A != null) A = A.next;
            else A = headB;
            if(B != null) B = B.next;
            else B = headA;
        }
        return A;
    }
}

//简化代码
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while(A != B){
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

进阶：你是否可以使用 O(1) 空间解决此题？

---

方法一：哈希表

遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode temp = head;
        while(temp != null){
            if(set.contains(temp)){
                return temp;
            }
            set.add(temp);
            temp = temp.next;
        }
        return null;
    }
}

时间复杂度：O(N)，其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。

空间复杂度：O(N)，其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。

方法二：快慢指针

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(true){
            if(fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

③栈&队列&堆

❶普通队列-Queue

队列是一种先进先出的数据结构，元素从后端入队，然后从前端出队。

Queue<> queue = new LinkedList<>();

常用方法

函数	功能
add(E e)/offer(E e)	压入元素
remove()/poll()	弹出元素
element()/peek()	获取队头元素
isEmpty()	用于检查此队列是“空”还是“非空”
size()	获取队列长度

❷双端队列-Deque

Java集合提供了接口Deque来实现一个双端队列，它的功能是：

• 既可以添加到队尾，也可以添加到队首；
• 既可以从队首获取，又可以从队尾获取。

Deque有三种用途

• 普通队列(一端进另一端出):

Deque<> queue = new LinkedList<>(); 
// 等价 
Queue<> queue = new LinkedList<>();

Queue方法	等效Deque方法
add(e)	addLast(e)
offer(e)	offerLast(e)
remove()	removeFirst()
poll()	pollFirst()
element()	getFirst()
peek()	peekFirst()

• 双端队列(两端都可进出)

//底层：ArrayDeque（动态数组）和 LinkedList（链表）
Deque<Integer> deque = new ArrayDeque<>();
Deque<Integer> deque = new LinkedList<>(); 

	第一个元素 (头部)	最后一个元素 (尾部)
插入	addFirst(e)/offerFirst(e)	addLast(e)/offerLast(e)
删除	removeFirst()/pollFirst()	removeLast()/pollLast()
获取	getFirst()/peekFirst()	getLast()/peekLast()

• 堆栈(先进后出)

//底层：ArrayDeque（动态数组）和 LinkedList（链表）
Deque<Integer> stack = new LinkedList<>(); 
Deque<Integer> stack = new ArrayDeque<>(); //速度更快
// 等价  
Stack<String> stack=new Stack<>();   

堆栈方法	等效Deque方法
push(e)	addFirst(e)
pop()	removeFirst()
peek()	peekFirst()

Deque所有方法

方法	描述
添加功能
push(E)	向队列头部插入一个元素,失败时抛出异常
addFirst(E)	向队列头部插入一个元素,失败时抛出异常
addLast(E)	向队列尾部插入一个元素,失败时抛出异常
offerFirst(E)	向队列头部加入一个元素,失败时返回false
offerLast(E)	向队列尾部加入一个元素,失败时返回false
获取功能
peek()	获取队列头部元素,队列为空时抛出异常
getFirst()	获取队列头部元素,队列为空时抛出异常
getLast()	获取队列尾部元素,队列为空时抛出异常
peekFirst()	获取队列头部元素,队列为空时返回null
peekLast()	获取队列尾部元素,队列为空时返回null
删除功能
removeFirstOccurrence(Object)	删除第一次出现的指定元素,不存在时返回false
removeLastOccurrence(Object)	删除最后一次出现的指定元素,不存在时返回false
弹出功能
pop()	弹出队列头部元素,队列为空时抛出异常
removeFirst()	弹出队列头部元素,队列为空时抛出异常
removeLast()	弹出队列尾部元素,队列为空时抛出异常
pollFirst()	弹出队列头部元素,队列为空时返回null
pollLast()	弹出队列尾部元素,队列为空时返回null

❸优先队列-PriorityQueue

优先级队列其实就是一个披着队列外衣的堆，因为优先队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。

PriorityQueue 是具有优先级别的队列，优先级队列的元素按照它们的自然顺序排序，或者由队列构造时提供的 Comparator 进行排序，这取决于使用的是哪个构造函数

构造函数	描述
PriorityQueue()	使用默认的容量（11）创建一个优队列，元素的顺序规则采用的是自然顺序
PriorityQueue(int initialCapacity)	使用默认指定的容量创建一个优队列，元素的顺序规则采用的是自然顺序
PriorityQueue(Comparator<? super E> comparator)	使用默认的容量队列，元素的顺序规则采用的是 comparator

//默认按自然顺序（升序）检索的
PriorityQueue<Integer> numbers = new PriorityQueue<>();

//使用Comparator接口自定义此顺序
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
  public int compare(int[] m, int[] n) {
    return m[1] - n[1];
  }
});

❹栈-Stack/Deque

栈是一种后进先出的数据结构，元素从顶端入栈，然后从顶端出栈。

注意：Java 堆栈 Stack 类已经过时，Java 官方推荐使用 Deque 替代 Stack 使用。Deque 堆栈操作方法：push()、pop()、peek()。

创建栈

//方法一，弃用
Stack<E> stack=new Stack<>();
Stack<String> stack=new Stack<>();

//方法二：推荐使用
//底层：ArrayDeque（动态数组）和 LinkedList（链表）
Deque stack = new ArrayDeque<String>();
Deque stack = new LinkedList<String>();

stack.push("a");
stack.pop();
stack.push("b");
System.out.println(stack);

常用方法

函数	功能
push(T t)	压栈（向栈顶放入元素）
pop()	出栈（拿出栈顶元素，并得到它的值）
peek()	将栈顶元素返回，但是不从栈中移除它
search(Object o)	返回对象在此堆栈上的从1开始的位置。
isEmpty()	判断栈是否为空
size()	获取栈长度

❺堆-Heap

堆通常可以被看做是一棵完全二叉树的数组对象。

堆的特性：

• 1.堆是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不是满的，那么要求左满右不满。

• 2.堆通常用数组来实现。将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子结点则分别在位置4,5,6和7，以此类推。(0被废弃)

如果一个结点的位置为k，则它的父结点的位置为[k/2]，而它的两个子结点的位置则分别为2k和2k+1。

这样，在不使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。

• 3.每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。

堆的API设计

public class Heap<T extends Comparable<T>> {
    //存储堆中的元素
    private T[] items;
    //记录堆中元素的个数
    private int N;

    public Heap(int capacity) {
        this.items = (T[]) new Comparable[capacity + 1];
        this.N = 0;
    }

    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return items[i].compareTo(items[j]) < 0;
    }

    //交换堆中i索引和j索引处的值
    private void exch(int i, int j) {
        T temp = items[i];
        items[i] = items[j];
        items[j] = temp;
    }

    //往堆中插入一个元素
    public void insert(T t) {
        items[++N] = t;
        swim(N);
    }

    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k) {
        //通过循环，不断的比较当前结点的值和其父结点的值，如果发现父结点的值比当前结点的值小，则交换位置
        while (k > 1) {
            //比较当前结点和其父结点
            if (less(k / 2, k)) {
                exch(k / 2, k);
            }
            k = k / 2;
        }
    }

    //删除堆中最大的元素,并返回这个最大元素
    public T delMax() {
        T max = items[1];
        //交换索引1处的元素和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根结点
        exch(1, N);
        //最大索引处的元素删除掉
        items[N] = null;
        //元素个数-1
        N--;
        //通过下沉调整堆，让堆重新有序
        sink(1);
        return max;
    }

    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void sink(int k) {
        //循环对比k结点和其左子结点2k以及右子结点2k+1处中的较大值的元素大小，如果当前结点小，则需要交换位置
        while (2 * k <= N) {
            //获取当前结点的子结点中的较大结点
            int max;//记录较大结点所在的索引
            if (2 * k + 1 <= N) {
                if (less(2 * k, 2 * k + 1)) {
                    max = 2 * k + 1;
                } else {
                    max = 2 * k;
                }
            } else {
                max = 2 * k;
            }
            //比较当前结点和较大结点的值
            if (!less(k, max)) {
                break;
            }
            //交换k索引处的值和max索引处的值
            exch(k, max);
            //变换k的值
            k = max;
        }
    }

    public static void main(String[] args) {
        Heap<String> heap = new Heap<String>(20);
        heap.insert("A");
        heap.insert("B");
        heap.insert("C");
        heap.insert("D");
        heap.insert("E");
        heap.insert("F");
        heap.insert("G");

        String del;
        //循环删除
        while ((del = heap.delMax()) != null) {
            System.out.print(del + ",");
        }
    }
}

❻LeetCode真题

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

• 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
• 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

---

class MyQueue {

    Deque<Integer> inStack;
    Deque<Integer> outStack;

    public MyQueue() {
         inStack = new ArrayDeque<>();   // 负责进栈
         outStack = new ArrayDeque<>(); // 负责出栈
    }
    
    public void push(int x) {
        inStack.push(x);
    }
    
    public int pop() {
        // 若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈
        if(outStack.isEmpty()){ 
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        // 弹出输出栈栈顶元素（输出栈不为空直接弹出，为空时执行上面操作）
        return outStack.pop();
    }
    
    public int peek() {
        // 若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈
        if(outStack.isEmpty()){ 
            while(!inStack.isEmpty()){
                outStack.push(inStack.pop());
            }
        }
        // 返回栈顶元素
        return outStack.peek();

    }
    
    public boolean empty() {
        return inStack.isEmpty() && outStack.isEmpty();
    }
}

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

---

class MyStack {

    Queue<Integer> queue1;
    Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList();   // 存储栈内的元素，
        queue2 = new LinkedList();   // 入栈操作的辅助队列
    }
    public void push(int x) {
        queue2.offer(x); //先存入queue2
        //把queue1的也存入queue2
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        //最后交换queue1和queue2，将元素都放到queue1中
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();

    }
    //queue1用于存储栈内的元素，因此只需要判断queue1是否为空即可
    public boolean empty() {
        return queue1.isEmpty();

    }
}

//一个队列实现栈
class MyStack {
  
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    //入栈操作时，首先获得入栈前的元素个数n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。
    public void push(int x) {
        int n = queue.size();
        queue.offer(x);
        for (int i = 0; i < n; i++) {
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

---

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        // 如果s的长度为奇数，一定不符合要求
        if (n % 2 == 1) return false;
        Map<Character, Character> map = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<>();
        for(int i = 0; i < n; i++){
            if(map.containsKey(s.charAt(i))){ //后括号则将对应前括号出栈
                if (stack.isEmpty() || stack.peek() != map.get(s.charAt(i))) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(s.charAt(i)); //前括号直接入栈
            }
        }
        return stack.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

---

//栈
class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for(char ch : s.toCharArray()){
            if(stack.isEmpty() || stack.peek() != ch){
                stack.push(ch);
            } else{
                stack.pop();
            }
        }
        String str = "";
        while(!stack.isEmpty()){
            str =stack.pop() +str;
        }
        return str;
    }
}

//数组
class Solution {
    public String removeDuplicates(String s) {
        char[] str = s.toCharArray();
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            if (top == -1 || str[top] != str[i]) {
                str[++top] = str[i];
            } else {
                top--;
            }
        }
        return String.valueOf(str, 0, top + 1);
    }
}

150. 逆波兰表达式求值

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：

输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

---

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
         for(String s : tokens){
            if ("+-*/".contains(s)) {
                int a = stack.pop();
                int b = stack.pop();
                if("+".equals(s))  stack.push(a + b);
                else if("-".equals(s))  stack.push(b - a);
                else if("*".equals(s))  stack.push(a * b);
                else if("/".equals(s))  stack.push(b / a);
            } else {
                stack.push(Integer.valueOf(s));
            }
         }
        return stack.pop();
    }
}

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
         for(String s : tokens){
            if ("+-*/".contains(s)) {
                int a = stack.pop();
                int b = stack.pop();
                switch(s){
                    case "+": 
                        stack.push(a + b);
                        break;
                    case "-": 
                        stack.push(b - a);
                        break;
                    case "*": 
                        stack.push(a * b);
                        break;
                    case "/": 
                        stack.push(b / a);
                        break;
                }
            } else {
                stack.push(Integer.valueOf(s));
            }
         }
        return stack.pop();
    }
}

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1]

---

方法一：优先队列

初始时，我们将数组 nums 的前 k 个元素和对应坐标放入优先队列中。

每当向右移动窗口时，就把新的元素放入优先队列中，此时堆顶的元素就是堆中所有元素的最大值。

特殊情况：到目前每次滑出窗口的元素并没有都从堆中删除，就会造成前面窗口的最大值一直在优先队列中，而窗口已经移走，最大值已经更换，前面窗口的最大值应该移出队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // 1. 优先队列存放的是二元组(num,index) 
        // num :   是为了比较元素大小
        // index : 是为了判断窗口的大小是否超出范围
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>(){
            public int compare(int[] pair1,int[] pair2){
                //大顶堆（元素大小不同按元素大小排列，元素大小相同按下标进行排列）
                return pair1[0] != pair2[0] ? pair2[0] - pair1[0]:pair2[1] - pair1[1];
            }
        });

        // 2. 优先队列初始化 : k个元素的堆
        for(int i = 0;i < k;i++){
            pq.offer(new int[]{nums[i], i});
        }

        // 3. 处理堆逻辑
        int[] res = new int[n - k + 1];            // 初始化结果数组长度 ：一共有 n - k + 1个窗口
        res[0] = pq.peek()[0];                    // 初始化res[0] ： 拿出目前堆顶的元素
        for(int i = k; i < n; i++){               // 向右移动滑动窗口
            pq.offer(new int[]{nums[i],i});      // 加入大顶堆中
            //特殊情况 当栈顶元素不在当前窗口范围就移除
            while(pq.peek()[1] <= i - k){       // 将栈顶下标不在滑动窗口中就干掉
                pq.poll();                      // 维护：堆的大小就是滑动窗口的大小
            }   
            res[i - k + 1] = pq.peek()[0];      // 此时堆顶元素就是滑动窗口的最大值
        }
        return res;
    }
}

方法二：单调队列

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length < 2){
            return nums;
        }
        // 维护一个单调递减的双端队列，存元素坐标(方便判断队首的值是否在窗口范围)
        Deque<Integer> deque = new LinkedList<>();
        // 存储最后返回结果
        int[] res = new int[nums.length - k + 1];

        for(int i = 0; i < nums.length; i++){
            // 清理不在窗口范围的元素
            if(!deque.isEmpty() && deque.peek() <= i - k){
                deque.pollFirst();
            }
            // 删除所有比新入队元素小的旧元素
            while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
                deque.pollLast();
            }
            // 新元素入队
            deque.addLast(i);
            // 当窗口长度为k时 开始保存窗口中最大值
            if(i + 1 >= k){
                res[i + 1 - k] = nums[deque.peekFirst()];
            }
        }
        return res;
    }
}

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

---

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
         // 队列按照键值对中的值（元素出现频率）从小到大排序
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        // 遍历map，用最小堆保存频率最大的k个元素
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}


class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计每个元素出现的次数，元素为键，元素出现的次数为值
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0) + 1);
        }

         // 队列按照键值对中的值（元素出现频率）从小到大排序
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        // 遍历map，用最小堆保存频率最大的k个元素
        for(Integer key : map.keySet()){
            if (queue.size() < k) {
                queue.offer(key);
            } else if (map.get(key) > map.get(queue.peek())) {
                queue.poll();
                queue.offer(key);
            }
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll();
        }
        return ret;
    }
}

④哈希表

❶基础知识

哈希表(Hash table)，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做哈希表。

常见的三种哈希结构

• 数组

int[] hashTable = new int[26]; //存26字母索引

//hashTable[s.charAt(i) - 'a']++; 字母存在则在对应位置加1

• set （集合）

Set<Integer> set = new HashSet<>();

//set.add(num) 插入元素
//set.contains(num) 查找键是否存在

• map（映射）

Map<Integer, Integer> map = new HashMap<>();

//map.put(key,value) 插入元素
//map.getOrDefault(ch, 0); 查询map是否存在ch,不存在设置默认值0
//map.values()  返回所有value
//map.containsKey(key) 查找键是否存在
//map.isEmpty() 判断是否为空
//map.get() 根据键获取值
//map.remove() 根据键删除映射关系

❷LeetCode真题

242. 有效的字母异位词

给定两个字符串 _s_ 和 _t_ ，编写一个函数来判断 _t_ 是否是 _s_ 的字母异位词。

注意：若 _s_ 和 _t_ 中每个字符出现的次数都相同，则称 _s_ 和 _t_ 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

---

方法1：哈希表

• 首先判断两个字符串长度是否相等，不相等则直接返回 false

• 若相等，则初始化 26 个字母哈希表，遍历字符串 s 和 t

• s 负责在对应位置增加，t 负责在对应位置减少

• 如果哈希表的值都为 0，则二者是字母异位词

//O(n)
class Solution {
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
        int[] hashTable = new int[26];
        for(int i = 0; i < s.length(); i++){
            hashTable[s.charAt(i) - 'a']++;
            hashTable[t.charAt(i) - 'a']--;
        }
        for(int i = 0; i < 26; i++){
            if(hashTable[i] != 0) 
                return false;
        }
        return true;
    }
}

方法2：排序
t 是 s 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s 和 t 分别排序，看排序后的字符串是否相等即可判断。此外，如果 s 和 t 的长度不同，t 必然不是 s 的异位词。

//O(nlog⁡n)
class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        Arrays.sort(str1);
        Arrays.sort(str2);
        return Arrays.equals(str1, str2);
    }
}

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""]
输出: [[""]]

示例 3:

输入: strs = ["a"]
输出: [["a"]]

---

方法1：排序

遍历字符串数组，对每个字符串中的字符排序，加入map对应的key的数组中。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for(String str : strs){
            char[] arr = str.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

方法2：计数
由于互为字母异位词的两个字符串包含的字母相同，因此两个字符串中的相同字母出现的次数一定是相同的，故可以将每个字母出现的次数使用字符串表示，作为哈希表的键。

由于字符串只包含小写字母，因此对于每个字符串，可以使用长度为 26 的数组记录每个字母出现的次数。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs) {
            int[] counts = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++) {
                counts[str.charAt(i) - 'a']++;
            }
            // 将每个出现次数大于 0 的字母和出现次数按顺序拼接成字符串，作为哈希表的键
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++) {
                if (counts[i] != 0) {
                    sb.append((char) ('a' + i));
                    sb.append(counts[i]);
                }
            }
            String key = sb.toString();
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

349. 两个数组的交集

给定两个数组 nums1 和 nums2 ，返回它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

---

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
      
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        //对nums1去重并存入set1
        for(int i = 0; i < nums1.length; i++){
            set1.add(nums1[i]);
        }
        //nums2与set对比，相同元素存入set2
        for(int num : nums2){
            if(set1.contains(num)){
                set2.add(num);
            }
        }
        //将set2转化为数组
        int[] res = new int[set2.size()];
        int index = 0;
        for(int num : set2){
            res[index++] = num;
        }
        //方法2:将set2转化为数组
        //int[] res = set2.stream().mapToInt(Integer::valueOf).toArray();
        return res;
    }
}

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2：

输入：n = 2
输出：false

---

1. 给一个数字 n，循环计算下一个数字，直到等于1
2. 使用Set判断我们是否进入了一个循环。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while(n != 1 && !set.contains(n)){
            set.add(n);
            n = getNextNum(n);
        }
        return n == 1;
    }

    public int getNextNum(int n) {
        int nextNum = 0;
        while(n > 0){
            int temp = n % 10;
            nextNum += temp * temp;
            n = n / 10;
        }
        return nextNum;
    }

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

---

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{map.get(target - nums[i]),i};
            }
            map.put(nums[i],i);
        }
        return new int[0];
    }
}

454. 四数相加 II

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

该题等价于 计算 a + b + c + d = 0

1. 首先定义 map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2. 遍历数组1和2，统计两个数组元素之和，和出现的次数，放到map中。
3. 定义int变量res，用来统计 a+b+c+d = 0 出现的次数。
4. 再遍历数组3和4，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value统计出来。
5. 最后返回统计值 res 就可以了

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        //key放两数之和，value放两数之和出现的次数。
        for(int i : nums1){
            for(int j: nums2){
                map.put(i + j, map.getOrDefault(i + j, 0) + 1);
            }
        }
        int res = 0;
        //如果在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。
        for(int i : nums3){
            for(int j: nums4){
                if(map.containsKey(0 - (i + j))){
                    res += map.get(0 - (i + j));
                }
            }
        }
        return res;
    }
}

383. 赎金信

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

---

//map实现
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character, Integer> map = new HashMap<>();
        for(char ch : magazine.toCharArray()){
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        for(char ch : ransomNote.toCharArray()){
            map.put(ch, map.getOrDefault(ch, 0) - 1);
        }
        for(Integer value : map.values() ){
            if(value < 0) return false;
        }
        return true;
    }
}
//哈希表实现
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] hashTable = new int[26];
        for(char ch : magazine.toCharArray()){
            hashTable[ch - 'a']++;
        }
        for(char ch : ransomNote.toCharArray()){
            hashTable[ch - 'a']--;
        }
        for(int value : hashTable){
            if(value < 0){
                return false;
            }
        }
        return true;
    }
}
//优化
class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] hashTable = new int[26];
        for (char ch : magazine.toCharArray()) {
            hashTable[ch - 'a']++;
        }
        // 合二为一
        for (char ch : ransomNote.toCharArray()) {
            if (--hashTable[ch - 'a'] < 0)
                return false;
        }
        return true;
    }
}

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

---

//三重暴力循环：超出时间限制
private List<List<Integer>> directlySolution(int[] nums) {
    if (nums == null || nums.length <= 2) {
        return Collections.emptyList();
    }
    Arrays.sort(nums);
    Set<List<Integer>> result = new LinkedHashSet<>();
    for (int i = 0; i < nums.length; i++) {
        for (int j = i+1; j < nums.length; j++) {
            for (int k = j+1; k < nums.length; k++) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> value = Arrays.asList(nums[i], nums[j], nums[k]);
                    result.add(value);
                }
            }
        }
    }

    return new ArrayList<>(result);
}

//两重暴力+hash
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        //把所有数组元素载入map
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        for(int i = 0; i < nums.length; i++){
            for(int j = i + 1; j < nums.length; j++){
                int c = 0 - (nums[i] + nums[j]);
                if(map.containsKey(c) && map.get(c) > j){
                    List<Integer> list = new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[j]);
                    list.add(c);
                    Collections.sort(list);//排序，方便去重
                    if(!result.contains(list)){
                        result.add(list);
                    }
                }  
            }
        }
        return result;
    }
}

//双指针
class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            //如果第一个就大于0，则三数之和一定大于0，结束循环
            if(nums[i] > 0) break; 
            //如果连续两个元素相等就跳过第二个，避免重复
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i + 1;
            int R = len - 1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if (sum < 0) L++;
                else if (sum > 0) R--;
                else if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L < R && nums[L] == nums[L+1]) L++; // 去重
                    while (L < R && nums[R] == nums[R-1]) R--; // 去重
                    L++;
                    R--;
                }
            }
        }        
        return ans;
    }
}

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

---

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0 && nums[i] > target) break; //去重
            if(i > 0 && nums[i] == nums[i -1]) continue; //去重
            for(int j = i + 1; j < nums.length; j++){
                if (j > i + 1 && nums[j - 1] == nums[j]) continue; //去重
                int L = j + 1, R = nums.length - 1;
                while(L < R) {
                    int sum = nums[i] + nums[j] + nums[L] + nums[R];
                    if(sum > target) R--;
                    else if(sum < target) L++;
                    else {
                        res.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
                        while(L < R && nums[L] == nums[L + 1]) L++; //去重
                        while(L < R && nums[R] == nums[R - 1]) R--; //去重
                        L++; 
                        R--;
                    }
                }  
            }
        }
        return res;
    }
}

⑤字符串

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

---

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while(left < right){
            char tmp  = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
    }
}
  
class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }
}
  
class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}  

541. 反转字符串 II

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2
输出："bacd"

---

题意：每隔2k个反转前k个，尾数不够k个时候全部反转

class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
        // 1. 每隔 2k 个字符的前 k 个字符进行反转
        for (int i = 0; i< n; i += 2 * k) {
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            if (i + k <= n) {
                reverse(arr, i, i + k -1);
                continue;
            }
            // 3. 剩余字符少于 k 个，则将剩余字符全部反转
            reverse(arr, i, n - 1);
        }
        return  new String(arr);
    }
    // 定义翻转函数
    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--;
        }
    }
}



class Solution {
    public String reverseStr(String s, int k) {
        int n = s.length();
        char[] arr = s.toCharArray();
      
        for (int i = 0; i < n; i += 2 * k) {
             // 1. 每隔 2k 个字符的前 k 个字符进行反转
            // 2. 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            reverse(arr, i, Math.min(i + k, n) - 1);
        }
        return String.valueOf(arr);
    }

    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--;
        }
    }
}

剑指 Offer 05. 替换空格

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

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

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ' '){
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }      
        return sb.toString();
    }
}

151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

---

class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

// 分割 + 倒序
class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if(strs[i].equals("")) continue; // 遇到空则跳过
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }
}

// 双指针
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(); // 转化为字符串并返回
    }
}

剑指 Offer 58 - II. 左旋转字符串

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

示例 1：

输入: s = "abcdefg", k = 2
输出: "cdefgab"

示例 2：

输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"

class Solution {
    public String reverseLeftWords(String s, int n) {
        StringBuilder sb = new StringBuilder();
        for(int i = n; i < s.length(); i++){
            sb.append(s.charAt(i));
        }
        for(int i = 0; i < n; i++){
             sb.append(s.charAt(i));
        }
        return sb.toString();
    }
}

class Solution {
    public String reverseLeftWords(String s, int n) {
        return s.substring(n, s.length()) + s.substring(0, n);
    }
}

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

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

---

暴力破解

class Solution {
    public int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        // 枚举原串的「发起点」
        for(int i = 0; i <= n - m; i++){
            boolean flag = true;
            for(int j = 0; j < m; j++){
                // 从原串的「发起点」和匹配串的「首位」开始，尝试匹配
                if(haystack.charAt(i + j) != needle.charAt(j)){
                    flag = false;
                    break;
                }
            }
            // 如果能够完全匹配，返回原串的「发起点」下标
            if(flag) return i;
        }
        return -1;
    }
}

KMP算法

class Solution {
    public static int strStr(String haystack, String needle) {
        int n = haystack.length(), m = needle.length();
        if (m == 0) return 0;

        // 1.构建 next 数组
        int[] next = new int[m]; //next[0]=0
        for (int i = 1, j = 0; i < m; i++) {
            // 匹配不成功的话，j = next(j-1)
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            // 匹配成功的话，j++
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            // 更新 next[i]
            next[i] = j;
        }

        // 2.匹配过程
        for (int i = 0, j = 0; i < n; i++) {
            // 匹配不成功 j = next(j-1)
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            // 匹配成功的话，j++
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}

459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

方法一：枚举

如果一个长度为 n 的字符串 s 可以由它的一个长度为 m 的子串 s′ 重复多次构成，那么：

• n 一定是 m 的倍数；
• s′ 一定是 s 的前缀；
• 对于任意的 i∈[m,n)，有 s[i] = s[i − m]。

小优化：因为子串至少需要重复一次，所以 m 不会大于 n 的一半，所以只需在 [1,n/2]的范围内枚举 m 即可。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for(int m = 1; m <= n/2; m++){
            if(n % m == 0){
                boolean match = true;
                for(int i = m; i < n; i++){
                    if(s.charAt(i) != s.charAt(i - m)) {
                        match = false;
                        break;
                    }
                }
                if(match){
                    return true;
                }
            }
        }
        return false;
    }
}

⑥双指针

344. 反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

---

class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while(left < right){
            char tmp  = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
    }
}
  
class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
        }
    }
}
  
class Solution {
    public void reverseString(char[] s) {
        int l = 0;
        int r = s.length - 1;
        while (l < r) {
            s[l] ^= s[r];  //构造 a ^ b 的结果，并放在 a 中
            s[r] ^= s[l];  //将 a ^ b 这一结果再 ^ b ，存入b中，此时 b = a, a = a ^ b
            s[l] ^= s[r];  //a ^ b 的结果再 ^ a ，存入 a 中，此时 b = a, a = b 完成交换
            l++;
            r--;
        }
    }
}  

27. 移除元素

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

//双指针
class Solution {
    public int removeElement(int[] nums, int val) {
        //快慢指针解法
        int slow = 0; //慢指针
        //快指针，无论与val值是否相同每遍历一次都要移动一位
        for(int fast = 0; fast < nums.length; fast++){
            //快指针先走，判断快指针指向的元素是否等于val
            if(nums[fast] != val){
                nums[slow] = nums[fast];
                slow++;  //只有当快指针不等于val的时候，慢指针才和快指针一起移动一位
            }
        }
        return slow;
    }
}

//通用解法
class Solution {
    public int removeElement(int[] nums, int val) {
        int idx = 0;
        for (int x : nums) {
            if (x != val) nums[idx++] = x;
        }
        return idx;
    }
}

剑指 Offer 05. 替换空格

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

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

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == ' '){
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }      
        return sb.toString();
    }
}

151. 反转字符串中的单词

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

---

class Solution {
    public String reverseWords(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }
}

// 分割 + 倒序
class Solution {
    public String reverseWords(String s) {
        String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
        StringBuilder res = new StringBuilder();
        for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
            if(strs[i].equals("")) continue; // 遇到空则跳过
            res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
        }
        return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }
}

// 双指针
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(); // 转化为字符串并返回
    }
}

206. 反转链表

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

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

//迭代法（双指针法）
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode tmp = null;
        while(cur != null){
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

// 递归法
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
    public ListNode reverse(ListNode pre, ListNode cur){
        if (cur == null) {
            return pre;
        }
        ListNode tmp = null;
        tmp = cur.next;
        cur.next = pre;
        return reverse(cur,tmp);
    }
}

//栈实现1(不推荐，效率不高)
class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> stack = new ArrayDeque<>();
        while(head != null){
            stack.push(head);
            head = head.next;
        }
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while(!stack.isEmpty()){
            temp.next = stack.pop();
            temp = temp.next;
        }
        temp.next = null; //最后节点不接null会形成环链
        return dummy.next;
    }
}
//栈实现2(不推荐，效率不高)
class Solution {
    public ListNode reverseList(ListNode head) {
        Deque<ListNode> stack = new ArrayDeque<>();
        while(head != null){
            stack.add(head);
            head = head.next;
        }
        ListNode dummy = new ListNode(0),
        ListNode temp = dummy;
        while(stack.size() != 0){
            temp.next = new ListNode(stack.pop());//防止形成环链
            temp = temp.next;
        }
        return dummy.next;
    }
}

26. 删除有序数组中的重复项

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

//双指针
class Solution {
    public int removeDuplicates(int[] nums) {
         //快慢指针解法
        int slow = 0; //慢指针
        //快指针，无论与val值是否相同每遍历一次都要移动一位
        for(int fast = 0; fast < nums.length; fast++){
            //快指针先走，判断快指针指向的元素是否等于val
            if(nums[fast] != nums[slow]){
                nums[++slow] = nums[fast];
            }
        }
        return slow + 1;
    }
}

class Solution {
    public int removeDuplicates(int[] nums) {   
        int idx = 0; 
        for (int x : nums) {
            if (idx < 1 || nums[idx - 1] != x) 
                nums[idx++] = x;
        }
        return idx;
    }
}

//通用解法
class Solution {
    public int removeDuplicates(int[] nums) {   
        return process(nums, 1);
    }
    //保留 k 个相同数字
    int process(int[] nums, int k) {
        int idx = 0; 
        for (int x : nums) {
            if (idx < k || nums[idx - k] != x) 
              nums[idx++] = x;
        }
        return idx;
    }
}

面试题 02.07. 链表相交

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

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

示例 2：

输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA;
        ListNode B = headB;
        while(A != B){
            if(A != null) A = A.next;
            else A = headB;
            if(B != null) B = B.next;
            else B = headA;
        }
        return A;
    }
}

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

进阶：你是否可以使用 O(1) 空间解决此题？

---

方法一：哈希表

遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        ListNode temp = head;
        while(temp != null){
            if(set.contains(temp)){
                return temp;
            }
            set.add(temp);
            temp = temp.next;
        }
        return null;
    }
}

时间复杂度：O(N)，其中 N 为链表中节点的数目。我们恰好需要访问链表中的每一个节点。

空间复杂度：O(N)，其中 N 为链表中节点的数目。我们需要将链表中的每个节点都保存在哈希表当中。

方法二：快慢指针

双指针第一次相遇： 设两指针 fast，slow 指向链表头部 head，fast 每轮走 2 步，slow 每轮走 1 步；

1. 第一种结果： fast 指针走过链表末端，说明链表无环，直接返回 null；
2. 第二种结果： 当fast == slow时， 两指针在环中 第一次相遇 。

双指针第二次相遇：

• slow指针 位置不变 ，将fast指针重新 指向链表头部节点 ；slow和fast同时每轮向前走 1 步；
• 当 fast 指针走到链表环入口，两指针重合。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(true){
            if(fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        fast = head;
        while(fast != slow){
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

15. 三数之和

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

---

//双指针
class Solution {
    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList();
        int len = nums.length;
        if(nums == null || len < 3) return ans;
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len ; i++) {
            //如果第一个就大于0，则三数之和一定大于0，结束循环
            if(nums[i] > 0) break; 
            //如果连续两个元素相等就跳过第二个，避免重复
            if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
            int L = i + 1;
            int R = len - 1;
            while(L < R){
                int sum = nums[i] + nums[L] + nums[R];
                if (sum < 0) L++;
                else if (sum > 0) R--;
                else if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L < R && nums[L] == nums[++L]); // 去重
                    while (L < R && nums[R] == nums[--R]); // 去重
                }
            }
        }        
        return ans;
    }
}

18. 四数之和

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

---

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            //nums[i] < 0时不一定得去重
            //数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过
            if(nums[i] > 0 && nums[i] > target) break; //去重
            if(i > 0 && nums[i] == nums[i - 1]) continue; //去重
            for(int j = i + 1; j < nums.length; j++){
                if (j > i + 1 && nums[j - 1] == nums[j]) continue; //去重
                int L = j + 1, R = nums.length - 1;
                while(L < R) {
                    int sum = nums[i] + nums[j] + nums[L] + nums[R];
                    if(sum > target) R--;
                    else if(sum < target) L++;
                    else {
                        res.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
                        while(L < R && nums[L] == nums[L + 1]) L++; //去重
                        while(L < R && nums[R] == nums[R - 1]) R--; //去重
                        L++; 
                        R--;
                    }
                }  
            }
        }
        return res;
    }
}

⑦二叉树

二叉树基础知识请参考：数据结构-树 | 简言之 (jwt1399.top)

//Definition for a binary tree node.
public class TreeNode {
    int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
      }
}

我们有一棵二叉树：

               根
              /  \
             左   右

栈是一种 先进后出的结构，那么入栈顺序必须调整为倒序

• 前序遍历，出栈顺序：根左右; 入栈顺序：右左根
• 中序遍历，出栈顺序：左根右; 入栈顺序：右根左
• 后序遍历，出栈顺序：左右根; 入栈顺序：根右左

❶二叉树遍历

144. 二叉树的前序遍历

先输出父节点，再遍历左子树和右子树

1.递归

/**
 *时间：O(n)
 *空间：O(h)
**/
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    public void dfs(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }
        res.add(root.val);
        dfs(root.left, res);
        dfs(root.right, res);
    }
}

2.迭代

1. 弹栈顶入列表
2. 如有右，先入右
3. 如有左，再入左

/**
 *时间：O(n)
 *空间：O(h)
**/
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();// 用栈来实现迭代
        if(root == null) {
          return res;
        }
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode tmp = stack.pop();
            res.add(tmp.val);
            if(tmp.right != null){ //先进右节点，后出
                stack.push(tmp.right);
            }
            if(tmp.left != null){ //后进左节点，先出
                stack.push(tmp.left);
            }
        }
        return res;
    } 
}

3.Morris

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：

/**
 *时间：O(n)
 *空间：O(1)
**/

94. 二叉树的中序遍历

先遍历左子树，再输出父节点，再遍历右子树

1.递归

/**
 *时间：O(n)
 *空间：O(h)
**/
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }
    public void inorderRecur(TreeNode root, List<Integer> res){
        if(root == null){
            return;
        }
        dfs(root.left, res);
        res.add(root.val);
        dfs(root.right, res);
    }
}

2.迭代

1. 根结点不为空，入栈并向左走。整条界依次入栈
2. 根结点为空，弹栈顶打印，向右走。

/**
 *时间：O(n)
 *空间：O(h)
**/
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while (root != null || !stack.isEmpty()) { 
            while (root != null) { // 将根和左子树入栈
                stack.push(root);
                root = root.left;
            }
            TreeNode tmp = stack.pop(); 
            res.add(tmp.val);
            root = tmp.right;
        }
        return res;
    }
}

3.Morris

。。。

145. 二叉树的后序遍历

先遍历左子树，再遍历右子树，最后输出父节点

1.递归

/**
 *时间：O(n)
 *空间：O(h)
**/
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        dfs(root, res);
        return res;
    }

    public void dfs(TreeNode root ,List<Integer> res){
        if(root == null){
            return;
        }
        dfs(root.left, res);
        dfs(root.right, res);
        res.add(root.val);
    }
}

2.迭代

1. 弹栈顶输出
2. 如有左，压入左
3. 如有右，压入右

/**
 *时间：O(n)
 *空间：O(h)
**/
class Solution {
  public List<Integer> postorderTraversal(TreeNode root) {
          List<Integer> res = new ArrayList<>();
          if (root == null) {
              return res;
          }
          Deque<TreeNode> stack = new LinkedList<>();
          TreeNode prev = null;
          while (!stack.isEmpty() || root != null) {
              while (root != null) { // 将左子树全部入栈
                  stack.push(root);
                  root = root.left;
              }
              root = stack.pop(); // 拿取栈顶节点
              if (root.right == null || root.right == prev) {
                  res.add(root.val);
                  prev = root;
                  root = null;
              } else {
                  // 重新把根节点入栈，处理完右子树还要回来处理根节点
                  stack.push(root);
                  // 当前节点为右子树
                  root = root.right;
              }
          }
          return res;
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        if(root == null){
            return res;
        }
        // 如果当前处理节点不为空或者栈中有数据则继续处理
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode tmp = stack.pop();
            res.add(tmp.val);
            if(tmp.left != null) stack.push(tmp.left);
            if(tmp.right != null) stack.push(tmp.right); //出栈根右左
        }
        Collections.reverse(res);//反转之后：左右根
        return res;
    }
}    

3.Morris

102. 二叉树的层序遍历

1.递归

/**
 *时间：O(n)
 *空间：O(h)
**/
class Solution {
  public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        dfs(root, 0, res);
        return res;
    }

    public void dfs(TreeNode root, Integer deep, List<List<Integer>> res) {
        if (root == null) return;
        deep++;
        if (res.size() < deep) {
            //当层级增加时，res的Item也增加
            List<Integer> item = new ArrayList<Integer>();
            res.add(item);
        }
        //利用res的索引值进行层级界定
        res.get(deep - 1).add(root.val);

        dfs(root.left, deep, res);
        dfs(root.right, deep, res);
    }
}

2.迭代

/**
 *时间：O(n)
 *空间：O(n)
**/
//借助队列
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }
}

❷二叉树深度

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

---

1.递归

// 左子树和右子树的最大深度 l 和 r，那么该二叉树的最大深度即为 max⁡(l,r)+1
// 时间复杂度：O(N)
// 空间复杂度：O(H)
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } 
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

2.迭代

// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int count = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            count++;
            for(int i = 0; i < n; i++){
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return count;
    }
}

559. N 叉树的最大深度

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

---

1.递归

class Solution {
    public int maxDepth(Node root) {
        if(root == null){
            return 0;
        }
        int depth = 0;
        if(root.children != null){
            for(Node child : root.children){
                depth = Math.max(depth, maxDepth(child));
            }
        }
        return depth + 1;   
    }
}

2.迭代

// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
    public int maxDepth(Node root) {
        if(root == null){
            return 0;
        }
        int depth = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            depth++;
            for(int i = 0; i < n; i++){
                Node node = queue.poll();
                if(node.children != null) {
                    for(Node child : node.children){
                        queue.offer(child);
                    }
                } 
            }
        }
        return depth; 
    }
}

111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

---

1.递归

// 时间复杂度：O(N)
// 空间复杂度：O(H)
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        //这道题递归条件里分为三种情况
        //1.左孩子和右孩子都为空的情况，说明到达了叶子节点，直接返回1即可
        if(root.left == null && root.right == null) return 1;
      
        //2.如果左孩子和右孩子其中一个为空，那么需要返回比较大的那个孩子的深度        
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //其中一个节点为空，说明m1和m2有一个必然为0，所以可以返回m1 + m2 + 1;
        if(root.left == null || root.right == null) return m1 + m2 + 1;
        
        //3.最后一种情况，也就是左右孩子都不为空，返回最小深度+1即可
        return Math.min(m1, m2) + 1; 
    }
}

//优化
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        int m1 = minDepth(root.left);
        int m2 = minDepth(root.right);
        //1.如果左孩子和右孩子有为空的情况，直接返回m1+m2+1
        //2.如果都不为空，返回较小深度+1
        return root.left == null || root.right == null ? m1 + m2 + 1 : Math.min(m1,m2) + 1;
    }
}

2.迭代

// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        int depth = 1;
        queue.offer(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            depth++;
            while(n > 0){
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
                if(node.left == null && node.right == null){
                    return depth;
                }
                n--;
            }
        }
        return depth;
    }
}

❸二叉树属性

226. 翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：

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

示例 3：

输入：root = []
输出：[]

---

1.递归

// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
    public TreeNode invertTree(TreeNode root) {
        traverse(root);
        return root;
    }

    public void traverse(TreeNode root){
        if(root == null){
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;

        traverse(root.left);
        traverse(root.right);
    }
}

//优化
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

2.迭代

//层序遍历
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null) {
            return null;
        }
        //将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            //每次都从队列中拿一个节点，并交换这个节点的左右子树
            TreeNode tmp = queue.poll();
            TreeNode left = tmp.left;
            tmp.left = tmp.right;
            tmp.right = left;
            //如果当前节点的左子树不为空，则放入队列等待后续处理
            if(tmp.left!=null) {
                queue.add(tmp.left);
            }
            //如果当前节点的右子树不为空，则放入队列等待后续处理
            if(tmp.right!=null) {
                queue.add(tmp.right);
            }
            
        }
        //返回处理完的根节点
        return root;
    }
}

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

---

1.递归

// 递归
// 时间复杂度：O(N)
// 空间复杂度：O(H)
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return check(root.left, root.right);
    }

    // 检查两棵子树是否对称
    boolean check(TreeNode left, TreeNode right){
        //递归的终止条件
        //两个节点都为空
            //或者两个节点中有一个为空
            //或者两个节点的值不相等
        if(left == null && right == null) return true;
        if(left == null || right == null) return false;
        if(left.val != right.val) return false;
        // 左右子节点需要对称相同
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

//优化
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return check(root.left, root.right);
    }
    boolean check(TreeNode left, TreeNode right){
        if (left == null || right == null) return left == right;
        if(left.val != right.val) return false;
        return check(left.left, right.right) && check(left.right, right.left);
    }
}

2.迭代

// 时间复杂度：O(N)
// 空间复杂度：O(N)
class Solution {
    public boolean isSymmetric(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        //将根节点的左右孩子放到队列中
        queue.offer(root.left);
        queue.offer(root.right);
        while(queue.size() > 0) {
            //从队列中取出两个节点，再比较这两个节点
            TreeNode left = queue.poll();
            TreeNode right = queue.poll();
            //如果两个节点都为空就继续循环，两者有一个为空就返回false
            if(left == null && right == null) {
                continue;
            }
            if(left == null || right == null) {
                return false;
            }
            if(left.val != right.val) {
                return false;
            }
            //将左节点的左孩子， 右节点的右孩子放入队列
            queue.offer(left.left);
            queue.offer(right.right);
            //将左节点的右孩子，右节点的左孩子放入队列
            queue.offer(left.right);
            queue.offer(right.left);
        }
        return true;
    }
}

110. 平衡二叉树

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：true

示例 2：

输入：root = [1,2,2,3,3,null,null,4,4]
输出：false

示例 3：

输入：root = []
输出：true

---

1.从顶至底（暴力法）

// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        if (Math.abs(height(root.left) - height(root.right)) > 1) {
            return false;
        }
        return isBalanced(root.left) && isBalanced(root.right);   
    }
  
    //节点高度
    int height(TreeNode root){
        if (root == null) return 0;
        int lHeight = height(root.left);
        int rHeight = height(root.right);
        return Math.max(lHeight, rHeight) + 1;
    }
}

2.从底至顶（提前阻断）

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    int height(TreeNode root) {
        if (root == null) return 0;
        int lHeight = height(root.left);
        int rHeight = height(root.right);
        // 如果一棵子树是平衡的，则返回其高度，否则返回 −1。
       // 如果存在一棵子树不平衡，则整个二叉树一定不平衡。
        if (lHeight == -1 || rHeight == -1 || Math.abs(lHeight - rHeight) > 1) {
            return -1;
        } else {
            return Math.max(lHeight, rHeight) + 1;
        }
    }
}

199. 二叉树的右视图

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

示例 2:

输入: [1,null,3]
输出: [1,3]

示例 3:

输入: []
输出: []

1.BFS

用 BFS 层序遍历算法，每一层的最后一个节点就是二叉树的右侧视图。我们可以把 BFS 反过来，从右往左遍历每一行，进一步提升效率。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            // 每一层头部就是最右侧的元素
            TreeNode last = queue.peek();
            for(int i =0; i < n; i++){
                TreeNode node = queue.poll();
                // 控制每一层从右向左遍历
                if(node.right != null) {
                    queue.offer(node.right);
                }
                if(node.left != null){
                    queue.offer(node.left);
                } 
            }
            res.add(last.val);
              
        }
        return res;
    }
}

2.DFS

用 DFS 递归遍历算法，同样需要反过来，先递归 root.right 再递归 root.left，同时用 res 记录每一层的最右侧节点作为右侧视图。

 class Solution {
  
    List<Integer> res = new ArrayList<>();
  
    public List<Integer> rightSideView(TreeNode root) {
        dfs(root, 0); // 从根节点开始访问，根节点深度是0
        return res;
    }

    private void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        // 先访问 当前节点，再递归地访问 右子树 和 左子树。
        if (depth == res.size()) {   
            res.add(root.val);
        }
        depth++;
        dfs(root.right, depth);
        dfs(root.left, depth);
    }
}

❹二叉树路径

解题模版：

//一般路径
List<String> res = new ArrayList<>();
List<int> path = new ArrayList<>();
void dfs(TreeNode root) {
    //如果为空，直接返回
    if (root == null) {
      return;
    }
    path.add(root.val);
    //如果是叶子节点，说明找到了一条路径，把它加入到res中
    if (root.left == null && root.right == null) {
      res.add(new ArrayList(path));
    }
    
    //如果不是叶子节点，在分别遍历他的左右子节点
    dfs(root.left);
    dfs(root.right);
  }
}

//给定和的路径
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
void dfs(TreeNode root, int targetSum){
  if (root == null) {
    return;
  }
  path.add(root.val);
  //如果是叶子节点，且路径和等于targetSum则添加到res
  if (root.left == null && root.right == null) {
    if(targetSum == root.val){
      res.add(new ArrayList(path));
      //因为res里面那个path和你后续修改的那个path指向的是同一块内存区域，
      //所以你对path进行修改，也会把res里的结果给修改掉
    }
  }
  dfs(root.left, targetSum - root.val);
  dfs(root.right, targetSum - root.val);
  path.remove(path.size() - 1); //删除该集合最后一个元素,实现path的复用
}

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

示例 1：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

示例 2：

输入：root = [1]
输出：["1"]

---

1.深度优先

// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        dfs(root, "", res);
        return res;
    }

    private void dfs(TreeNode root, String path, List<String> res) {
         //如果为空，直接返回
         if (root == null) return;
         //如果是叶子节点，说明找到了一条路径，把它加入到res中
         if (root.left == null && root.right == null) {
             res.add(path + root.val);
             return;
         }
         //如果不是叶子节点，在分别遍历他的左右子节点
         dfs(root.left, path + root.val + "->", res);
         dfs(root.right, path + root.val + "->", res);
    }
}


class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new LinkedList<>();
        if (root == null) return res;
        //到达叶子节点，把路径加入到集合中
        if (root.left == null && root.right == null) {
            res.add(root.val + "");
            return res;
        }
        //遍历左子节点的路径
        for (String path : binaryTreePaths(root.left)) {
            res.add(root.val + "->" + path);
        }
        //遍历右子节点的路径
        for (String path : binaryTreePaths(root.right)) {
            res.add(root.val + "->" + path);
        }
        return res;
    }
}

2.广度优先

// 时间复杂度：O(n^2)
// 空间复杂度：O(n^2)
// 使用一个队列
class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null)
            return res;
        //队列，节点和路径成对出现，路径就是从根节点到当前节点的路径
        Queue<Object> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root.val + "");
        while (!queue.isEmpty()) {
            TreeNode node = (TreeNode) queue.poll();
            String path = (String) queue.poll();
            //如果到叶子节点，说明找到了一条完整路径
            if (node.left == null && node.right == null) {
                res.add(path);
            }

            //右子节点不为空就把右子节点和路径存放到队列中
            if (node.right != null) {
                queue.offer(node.right);
                queue.offer(path + "->" + node.right.val);
            }

            //左子节点不为空就把左子节点和路径存放到队列中
            if (node.left != null) {
                queue.offer(node.left);
                queue.offer(path + "->" + node.left.val);
            }
        }
        return res;
    }
}


// 使用两个队列
class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> paths = new ArrayList<String>();
        if (root == null) {
            return paths;
        }
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<String> pathQueue = new LinkedList<String>();

        nodeQueue.offer(root);
        pathQueue.offer(Integer.toString(root.val));

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll(); 
            String path = pathQueue.poll();

            if (node.left == null && node.right == null) {
                paths.add(path);
            } 
            if (node.left != null) {
              nodeQueue.offer(node.left);
              //pathQueue.offer(path + "->" + node.left.val);
              pathQueue.offer(new StringBuffer(path).append("->").append(node.left.val).toString());
            }

            if (node.right != null) {
              nodeQueue.offer(node.right);
              //pathQueue.offer(path + "->" + node.right.val);
              pathQueue.offer(new StringBuffer(path).append("->").append(node.right.val).toString());
            }
        }
        return paths;
    }
}

112. 路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

1.深度优先

// 时间复杂度：O(n)
// 空间复杂度：O(h)
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

//遍历所有路径，并保存所有路径和
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<Integer> res = new ArrayList<>();
        dfs(root, 0, res);
        for(int i : res){
            if(i == targetSum){
                return true;
            }  
        }
        return false;
    }

    private void dfs(TreeNode root, int sum, List<Integer> res) {
         if (root == null) return;
         //如果是叶子节点，说明找到了一条路径，把它加入到res中
         if (root.left == null && root.right == null) {
             res.add(sum + root.val);
             return;
         }
         //如果不是叶子节点，在分别遍历他的左右子节点
         dfs(root.left, sum + root.val , res);
         dfs(root.right, sum + root.val , res);
    }
}


class Solution {
    List<Integer> res = new ArrayList<>();
    boolean flag = false;
    public boolean hasPathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return flag;
    }

    private void dfs(TreeNode root, int targetSum) {
         if (root == null) {
             return;
         }
         //说明找到了一条和为targetSum的路径
         if (root.left == null && root.right == null) {
             if(targetSum == root.val){
                flag = true;
             }
         }
         //如果不是叶子节点，在分别遍历他的左右子节点
         dfs(root.left, targetSum - root.val);
         dfs(root.right, targetSum - root.val);
    }
}

2.广度优先

// 时间复杂度：O(n)
// 空间复杂度：O(n)
// 使用一个队列
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return false;
        Queue<Object> queue = new LinkedList<>();
        queue.offer(root);
        queue.offer(root.val);
        while (!queue.isEmpty()) {
            TreeNode node = (TreeNode) queue.poll();
            int path = (int) queue.poll();
            //如果到叶子节点，说明找到了一条完整路径
            if (node.left == null && node.right == null) {
                res.add(path);
              
            }

            //右子节点不为空就把右子节点和路径存放到队列中
            if (node.right != null) {
                queue.offer(node.right);
                queue.offer(path + node.right.val);
            }

            //左子节点不为空就把左子节点和路径存放到队列中
            if (node.left != null) {
                queue.offer(node.left);
                queue.offer(path + node.left.val);
            }
        }
        for(int i : res){
            if(i == targetSum){
                return true;
            }  
        }
        return false;
    }
}

// 使用两个队列
class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queNode = new LinkedList<TreeNode>();
        Queue<Integer> queVal = new LinkedList<Integer>();
        queNode.offer(root);
        queVal.offer(root.val);
        while (!queNode.isEmpty()) {
            TreeNode now = queNode.poll();
            int temp = queVal.poll();
            if (now.left == null && now.right == null) {
                if (temp == sum) {
                    return true;
                }
                continue;
            }
            if (now.left != null) {
                queNode.offer(now.left);
                queVal.offer(now.left.val + temp);
            }
            if (now.right != null) {
                queNode.offer(now.right);
                queVal.offer(now.right.val + temp);
            }
        }
        return false;
    }
}

113. 路径总和 II

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

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：[]

示例 3：

输入：root = [1,2], targetSum = 0
输出：[]

---

1.深度优先

// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return res;

    }
    void dfs(TreeNode root, int targetSum){
        if (root == null) {
            return;
        }
        path.add(root.val);
        //如果是叶子节点，且路径和等于targetSum则添加到res
        if (root.left == null && root.right == null) {
            if(targetSum == root.val){
                res.add(new ArrayList(path));
                //因为res里面那个path和你后续修改的那个path指向的是同一块内存区域，
                    //所以你对path进行修改，也会把res里的结果给修改掉
            }
        }
        dfs(root.left, targetSum - root.val);
        dfs(root.right, targetSum - root.val);
        path.remove(path.size() - 1); //删除该集合最后一个元素,实现path的复用
    }
}

2.广度优先

// 时间复杂度：O(n^2)
// 空间复杂度：O(n)
class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        //使用两个队列，一个存储结点，一个存储从根结点到当前节点的路径
        Queue<TreeNode> nodeQueue = new LinkedList<>();
        Queue<List<Integer>>  pathQueue = new LinkedList<>();
        //根节点入队
        nodeQueue.offer(root);
        //根节点的路径入队
        List<Integer> pathList = new ArrayList<>();
        pathList.add(root.val);
        pathQueue.offer(pathList);

        while(!nodeQueue.isEmpty()){
            //当前节点出队
            TreeNode node = nodeQueue.poll();
            //当前节点的路径出队
            List<Integer> tempList = pathQueue.poll();
            
             //如果满足条件，就把路径存储到res中
            if(node.left == null && node.right == null){
               
                int pathSum = 0;
                for(int i : tempList){
                    pathSum += i;
                }

                if(pathSum == targetSum){
                    res.add(tempList);
                }
            }
             //左子节点不为空，左子节点和路径入队
            if(node.left != null){
                nodeQueue.offer(node.left);
                tempList.add(node.left.val);
                pathQueue.offer(new ArrayList<>(tempList));
                tempList.remove(tempList.size() - 1);//？？？

            }
            if(node.right != null){
                nodeQueue.offer(node.right);
                tempList.add(node.right.val);
                pathQueue.offer(new ArrayList<>(tempList));
            }
        }
        return res;
    }
}

437. 路径总和 III

面试题 04.12. 求和路径

988. 叶结点开始的最小字符串

129. 根节点到叶节点数字之和

124. 二叉树中的最大路径和

687. 最长同值路径

543. 二叉树的直径

❺二叉树节点

404. 左叶子之和

给定二叉树的根节点 root ，返回所有左叶子之和。

示例 1：

输入: root = [3,9,20,null,null,15,7] 
输出: 24 
解释: 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24

示例 2:

输入: root = [1]
输出: 0

1.深度优先

class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        dfs(root);
        return sum;
    }
    int sum = 0;
    void dfs(TreeNode root){
        if(root == null){
            return;
        }
        if (root.left != null && root.left.left == null && root.left.right == null) {
            // 找到左侧的叶子节点，记录累加值
            sum += root.left.val;
        }
        dfs(root.left);
        dfs(root.right);

    }
}

2.广度优先

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while(!queue.isEmpty()){
            int n = queue.size();
            for(int i = 0; i < n; i++){
                TreeNode node = queue.poll();
                if(node.left != null) {
                    //判断叶子节点
                    if (node.left.left == null && node.left.right == null) {
                        sum += node.left.val;
                    } else {
                        queue.offer(node.left);
                    }
                    
                }
                if(node.right != null) queue.offer(node.right);
            }
        }
        return sum;
    }
}

//不分层
class Solution {
    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node.left != null) {
                //判断叶子节点
                if (node.left.left == null && node.left.right == null) {
                    sum += node.left.val;
                } else {
                    queue.offer(node.left);
                }
            }
            if(node.right != null) queue.offer(node.right);
        }
        return sum;
    }
}

513. 找树左下角的值

此题同：剑指 Offer II 045. 二叉树最底层最左边的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

---

1.广度优先

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if(root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()){
            int n = queue.size();
            for(int i = 0; i < n; i++){
                TreeNode node = queue.poll();
                if(i == 0){
                    res = node.val;
                }
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return res;

    }
}

//层序遍历，从右往左添加结点，最后访问的一个结点即为最后一层最左边的。
class Solution {
    public int findBottomLeftValue(TreeNode root) {
        int res = 0;
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.right != null) queue.offer(node.right);
            if (node.left != null) queue.offer(node.left);
            res = node.val; //最后访问的一个结点即为最后一层最左边的。
        }
        return res;
    }
}

2.深度优先

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {

    // 记录二叉树的最大深度
    int maxDepth = 0;
    // 返回结果
    int res = 0;

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 1);
        return res;
    }
    // depth 记录 dfs 递归遍历到的深度
    void dfs(TreeNode root, int depth){
        if(root == null){
            return;
        }
        if (depth > maxDepth) {
            // 到最大深度时第一次遇到的节点就是左下角的节点
            maxDepth = depth;
            res = root.val;
        }
        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}

1302. 层数最深叶子节点的和

给你一棵二叉树的根节点 root ，请你返回 层数最深的叶子节点的和 。

示例 1：

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

示例 2：

输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出：19

1.广度优先

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        if(root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int sum = 0;
        while(!queue.isEmpty()){
            int n = queue.size();
            sum = 0;
            for(int i = 0; i < n; i++){
                TreeNode node = queue.poll();
                sum += node.val; // 累加一层的节点之和
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return sum;
    }
}

2.深度优先

// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    int maxDepth = 0;
    int sum = 0;
    public int deepestLeavesSum(TreeNode root) {
        dfs(root, 1);
        return sum;
    }

    void dfs(TreeNode root, int depth){
        if(root == null){
            return;
        }
        if (depth > maxDepth) {
            // 到最大深度时第一次遇到的节点就是左下角的节点
            maxDepth = depth;
            sum = root.val;
        } else if(depth == maxDepth) {
            // 累加之后的节点值
            sum += root.val;
        }

        dfs(root.left, depth + 1);
        dfs(root.right, depth + 1);
    }
}

222. 完全二叉树的节点个数

给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2^h 个节点。

示例 1：

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

示例 2：

输入：root = []
输出：0

示例 3：

输入：root = [1]
输出：1

---

1.递归

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

//优化
// 利用满二叉树的性质来进行求解
public int countNodes(TreeNode root) {
    if(root == null) return 0;
    // 返回左右子树的高度
    int left = countLevel(root.left);
    int right = countLevel(root.right);
    if(left == right){
        // 说明左侧为满二叉树，[1 << left == (int)Math.pow(2, left)]
        return countNodes(root.right) + (1 << left);
     } else{
        // 说明右侧为满二叉树
        return countNodes(root.left) + (1 << right);
    }
}
// 计算高度
int countLevel(TreeNode root) {
    int level = 0;
    while(root != null){
      root = root.left;
      level++;
    }
    return level;
}

2.迭代

class Solution {
    public int countNodes(TreeNode root) {
        if(root == null){
            return 0;
        }
        int res = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int n = queue.size();
            res += n;
            for(int i = 0; i < n; i++){
                TreeNode node = queue.poll();
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return res;
    }
}

❻二叉树构建

106. 从中序与后序遍历序列构造二叉树

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

示例 1:

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

示例 2:

输入：inorder = [-1], postorder = [-1]
输出：[-1]

---

构造二叉树，第一件事一定是找根节点，然后想办法构造左右子树。

• 中序遍历的顺序：左孩子，根节点，右孩子。
• 后序遍历的顺序：左孩子，右孩子，根节点。

后序遍历结果最后一个就是根节点的值，然后再根据中序遍历结果确定左右子树的节点。

class Solution {
    // 存储 inorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }

    /*
       定义：
       中序遍历数组为 inorder[inStart..inEnd]，
       后序遍历数组为 postorder[postStart..postEnd]，
       构造这个二叉树并返回该二叉树的根节点
    */
    TreeNode build(int[] inorder, int inStart, int inEnd,
                int[] postorder, int postStart, int postEnd) {

        //终止条件，没有元素可构建，返回空
        if (inStart > inEnd) { 
            return null;
        }
        // root 节点对应的值就是后序遍历数组的最后一个元素
        int rootVal = postorder[postEnd];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex.get(rootVal);
        // 左子树的节点个数
        int leftSize = index - inStart;
        // 构造结点
        TreeNode root = new TreeNode(rootVal);

        // 递归构造左右子树
        root.left = build(inorder, inStart, index - 1,
                         postorder, postStart, postStart + leftSize - 1);
        
        root.right = build(inorder, index + 1, inEnd,
                          postorder, postStart + leftSize, postEnd - 1);
        return root;
    }
}

105. 从前序与中序遍历序列构造二叉树

本题与剑指 Offer 07. 重建二叉树 相同

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

---

构造二叉树，第一件事一定是找根节点，然后想办法构造左右子树。

前序遍历结果第一个就是根节点的值，然后再根据中序遍历结果确定左右子树的节点。

class Solution {
    // 存储 inorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            valToIndex.put(inorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    /*
       定义：前序遍历数组为 preorder[preStart..preEnd]，
       中序遍历数组为 inorder[inStart..inEnd]，
       构造这个二叉树并返回该二叉树的根节点
    */
    TreeNode build(int[] preorder, int preStart, int preEnd,
                   int[] inorder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return null;
        }

        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        // rootVal 在中序遍历数组中的索引
        int index = valToIndex.get(rootVal);
        // 左子树的节点个数
        int leftSize = index - inStart;

        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);

        // 递归构造左右子树
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                inorder, inStart, index - 1);

        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                inorder, index + 1, inEnd);
        return root;
    }
}

889. 根据前序和后序遍历构造二叉树

给定两个整数数组，preorder 和 postorder ，其中 preorder 是一个具有 无重复 值的二叉树的前序遍历，postorder 是同一棵树的后序遍历，重构并返回二叉树。

如果存在多个答案，您可以返回其中 任何 一个。

示例 1：

输入：preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
输出：[1,2,3,4,5,6,7]

示例 2:

输入: preorder = [1], postorder = [1]
输出: [1]

---

前序遍历和后序遍历是没办法唯一确定一个二叉树

1、首先把前序遍历结果的第一个元素或者后序遍历结果的最后一个元素确定为根节点的值。

2、然后把前序遍历结果的第二个元素作为左子树的根节点的值。

3、在后序遍历结果中寻找左子树根节点的值，从而确定了左子树的索引边界，进而确定右子树的索引边界，递归构造左右子树即可。

class Solution {
    // 存储 postorder 中值到索引的映射
    HashMap<Integer, Integer> valToIndex = new HashMap<>();
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for (int i = 0; i < postorder.length; i++) {
            valToIndex.put(postorder[i], i);
        }
        return build(preorder, 0, preorder.length - 1, postorder, 0, postorder.length - 1);
    }

     // 定义：根据 preorder[preStart..preEnd] 和 postorder[postStart..postEnd]
    // 构建二叉树，并返回根节点。
    TreeNode build(int[] preorder, int preStart, int preEnd, int[] postorder, int postStart, int postEnd) {
        if (preStart > preEnd) {
            return null;
        }
        // 单个节点判断
        // 因为要确定左子树的根节点，所以需要进行单个节点的判断
        // 如果只有一个节点，则不存在左右子树，更不存在左右子树的根节点了
        if (preStart == preEnd) {
            return new TreeNode(preorder[preStart]);
        }
       
        // root 节点对应的值就是前序遍历数组的第一个元素
        int rootVal = preorder[preStart];
        int leftRootVal = preorder[preStart + 1];
        // leftRootVal 在中序遍历数组中的索引
        int index = valToIndex.get(leftRootVal);
        // 左子树的节点个数
        int leftSize = index - postStart + 1;

        // 先构造出当前根节点
        TreeNode root = new TreeNode(rootVal);

        // 递归构造左右子树
        root.left = build(preorder, preStart + 1, preStart + leftSize,
                postorder, postStart, index);
        root.right = build(preorder, preStart + leftSize + 1, preEnd,
                postorder, index + 1, postEnd - 1);
        return root;
    }
}

654. 最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

1. 创建一个根节点，其值为 nums 中的最大值。
2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 最大二叉树 。

示例 1：

输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

输入：nums = [3,2,1]
输出：[3,null,2,null,1]

1.递归

//时间复杂度：O(n^2)
//空间复杂度：O(n)
class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    TreeNode build(int[] nums, int start, int end){
        if(start > end){
            return null;
        }
        // 找到数组中的最大值和对应的索引
        int maxVal = Integer.MIN_VALUE;
        int maxIndex = -1;
        for(int i = start; i <= end; i++){
            if(nums[i] > maxVal){
                maxVal = nums[i];
                maxIndex = i;
            }
        }
        TreeNode root = new TreeNode(maxVal);
        // 递归调用构造左右子树
        root.left = build(nums, start, maxIndex - 1);
        root.right = build(nums, maxIndex + 1, end);
        return root;
    }
}

2.单调栈(递减)

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new ArrayDeque();
        for (int i = 0; i < nums.length; i++) {
            TreeNode node = new TreeNode(nums[i]);
            while(!stack.isEmpty()) {
                TreeNode topNode = stack.peek();
                //如果栈顶元素大于待插入的元素，那么直接入栈
                //此时 栈顶元素.right = 待插入元素
                if (topNode.val > node.val) {
                    stack.push(node);
                    topNode.right = node;
                    break;
                //如果栈顶元素小于待插入的元素，那么栈顶元素出栈。
                //此时 待插入元素.left = 栈顶元素
                } else {
                    stack.pop();
                    node.left = topNode;
                }
            }
            if (stack.isEmpty()) stack.push(node);
        }
        // 返回栈底的元素，也就是最大值
        return stack.peekLast();
    }
}


class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        TreeNode[] deque = new TreeNode[1001];
        int tail = 0;
        for (int i = 0; i < nums.length; i++) {
            TreeNode node = new TreeNode(nums[i]);
            while(tail != 0) {
                TreeNode topNode = deque[tail - 1];
                if (topNode.val > node.val) {
                    deque[tail++] = node;
                    topNode.right = node;
                    break;
                } else {
                    deque[--tail] = null; // 出栈操作
                    node.left = topNode;
                }
            }
            if (tail == 0) deque[tail++] = node;
        }
        return deque[0];
    }
}

998. 最大二叉树 II

class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val < val) {
            // 如果 val 是整棵树最大的，那么原来的这棵树应该是 val 节点的左子树，
            // 因为 val 节点是接在原始数组 a 的最后一个元素
            TreeNode temp = root;
            root = new TreeNode(val);
            root.left = temp;
        } else {
            // 如果 val 不是最大的，那么就应该在右子树上，
            // 因为 val 节点是接在原始数组 a 的最后一个元素
            root.right = insertIntoMaxTree(root.right, val);
        }
        return root;
    }
}


class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        // 如果 val 是整棵树最大的，那么原来的这棵树应该是 val 节点的左子树
        if(root == null || root.val < val){
            return new TreeNode(val, root, null);
        }
        // 如果 val 不是最大的，那么就应该在右子树上
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}

617. 合并二叉树

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。

示例 1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

输入：root1 = [1], root2 = [1,2]
输出：[2,2] 

---

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            return root1;
        }
        TreeNode root = new TreeNode(root1.val + root2.val);
        root.left = mergeTrees(root1.left, root2.left);
        root.right = mergeTrees(root1.right, root2.right);
        return root;
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 如果一棵树有，另一棵树没有，接上去
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        // 两棵树都有的节点，叠加节点值
        root1.val += root2.val;
        // 递归合并左右子树
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

❼二叉树祖先

236. 二叉树的最近公共祖先

本题与剑指 Offer 68 - II. 二叉树的最近公共祖先 相同

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

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

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

---

解析：

1. 终止条件：
   1. 当越过叶节点，则直接返回 null ；
   2. 当 root 等于 p或q ，则直接返回 root ；
2. 递推工作：
   1. 开启递归左子节点，返回值记为 left；
   2. 开启递归右子节点，返回值记为 right ；
3. 返回值： 根据 left 和 right ，可展开为四种情况；
   1. 当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q ，返回 null；
   2. 当 left 和 right 同时不为空 ：说明 p,q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root ；
   3. 当 left 为空 ，right 不为空 ：p,q 都不在 root 的左子树中，直接返回 right 。具体可分为两种情况：
      1. p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ）；
      2. p,q 两节点都在 root 的 右子树 中，此时的 right 指向 最近公共祖先节点 ；
   4. 当 left 不为空 ， right 为空 ：与情况 3. 同理；

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // base case
        if (root == null) return null;
        if (root == p || root == q) return root;

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // 情况 1
          if (left == null && right == null) {
            return null;
        }
        // 情况 2
        if (left != null && right != null) {
            return root;
        }
        // 情况 3，4
        return left == null ? right : left;
    }
}

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

本题与剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 相同

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

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

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

---

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null) return null;
        // p 和 q 都在 root 的左子树，那么 LCA 在左子树
        if (root.val > q.val && root.val > p.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        // p 和 q 都在 root 的右子树，那么 LCA 在右子树
        if (root.val < q.val && root.val < p.val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        // p 和 q 分别在 root 的左右子树，那么 root 就是 LCA
        return root;
    }
}

❽二叉搜索树

中序遍历会有序遍历 BST 的节点

解题框架

void BST(TreeNode root, int target) {
        if (root == null) return;
    if (root.val == target) {
      // 找到目标，做点什么
    } 
    // 去右子树搜索
    if (root.val < target) {
      BST(root.right, target);
    }
    // 去左子树搜索 
    if (root.val > target) {
      BST(root.left, target);
    }     
}

700. 二叉搜索树中的搜索

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

输入：root = [4,2,7,1,3], val = 5
输出：[]

---

//递归
class Solution {
    public TreeNode searchBST(TreeNode root, int target) {
        if (root == null) {
            return null;
        }
        // 去左子树搜索
        if (root.val > target) {
            return searchBST(root.left, target);
        }
        // 去右子树搜索
        if (root.val < target) {
            return searchBST(root.right, target);
        }
        return root;
    }
}

//迭代
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while (root != null) {
            if (val == root.val) {
                return root;
            }
            root = val < root.val ? root.left : root.right;
        }
        return null;
    }
}

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。
• 节点的右子树只包含 大于 当前节点的数。
• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

---

误区：BST 不是左小右大么，那只要检查 root.val > root.left.val 且 root.val < root.right.val 不就行了？这样是不对的，因为 BST 左小右大的特性是指 root.val 要比左子树的所有节点都更大，要比右子树的所有节点都小，只检查左右两个子节点当然是不够的。

class Solution {
    boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    /* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
    boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
        // base case
        if (root == null) return true;
        // 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
        if (min != null && root.val <= min.val) return false;
        if (max != null && root.val >= max.val) return false;
        // 限定左子树的最大值是 root.val，右子树的最小值是 root.val
        return isValidBST(root.left, min, root) 
            && isValidBST(root.right, root, max);
    }
}

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

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

1. 首先找到需要删除的节点；
2. 如果找到了，删除它。

示例 1:

输入：root = [5,3,6,2,4,null,7], key = 3
输出：[5,4,6,2,null,null,7]
解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。
一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。
另一个正确答案是 [5,2,6,null,4,null,7]。

示例 2:

输入: root = [5,3,6,2,4,null,7], key = 0
输出: [5,3,6,2,4,null,7]
解释: 二叉树不包含值为 0 的节点

示例 3:

输入: root = [], key = 0
输出: []

---

情况 1：A 恰好是末端节点，两个子节点都为空，那么它可以当场去世了：

情况 2：A 只有一个非空子节点，那么它要让这个孩子接替自己的位置：

情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点或者右子树中最小的那个节点来接替自己，我的解法是用右子树中最小节点来替换：

//解题框架
TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (root.val == key) {
        // 找到啦，进行删除
    } else if (root.val > key) {
        // 去左子树找
        root.left = deleteNode(root.left, key);
    } else if (root.val < key) {
        // 去右子树找
        root.right = deleteNode(root.right, key);
    }
    return root;
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {
            // 这两个 if 把情况 1 和 2 都正确处理了
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;
            // 情况 3
            // 获得右子树最小的节点
            TreeNode minNode = getMin(root.right);
            // 删除右子树最小的节点
            root.right = deleteNode(root.right, minNode.val);
            // 用右子树最小的节点替换 root 节点
            minNode.left = root.left;
            minNode.right = root.right;
            root = minNode;
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

    TreeNode getMin(TreeNode node) {
        // BST 最左边的就是最小的
        while (node.left != null) node = node.left;
        return node;
    }
}

注意：

情况 3 时通过一系列略微复杂的链表操作交换 root 和 minNode 两个节点：

// 处理情况 3
// 获得右子树最小的节点
TreeNode minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
minNode.left = root.left;
minNode.right = root.right;
root = minNode;

有的读者可能会疑惑，替换 root 节点为什么这么麻烦，直接改 val 字段不就行了？看起来还更简洁易懂：

// 处理情况 3
// 获得右子树最小的节点
TreeNode minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
root.val = minNode.val;

仅对于这道算法题来说是可以的，但这样操作并不完美，我们一般不会通过修改节点内部的值来交换节点。因为在实际应用中，BST 节点内部的数据域是用户自定义的，可以非常复杂，而 BST 作为数据结构（一个工具人），其操作应该和内部存储的数据域解耦，所以我们更倾向于使用指针操作来交换节点，根本没必要关心内部数据。

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

给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果

示例 1：

输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]

示例 2：

输入：root = [40,20,60,10,30,50,70], val = 25
输出：[40,20,60,10,30,50,70,null,null,25]

示例 3：

输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
输出：[4,2,7,1,3,5]

---

//递归
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 找到空位置插入新节点
        if (root == null) return new TreeNode(val);
        // 去右子树搜索
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        }
        // 去左子树搜索 
        if (root.val > val) {
            root.left = insertIntoBST(root.left, val);
        }     
        return root;
    }
}

//迭代
class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;
    }
}

530. 二叉搜索树的最小绝对差

本题与783. 二叉搜索树节点最小距离相同

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

---

中序遍历会有序遍历 BST 的节点，遍历过程中计算最小差值即可。

使当前节点减去上个节点，比较差值，最小的就是答案。

class Solution {
    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return res;
    }

    TreeNode prev = null;// 记录上一个遍历的结点
    int res = Integer.MAX_VALUE;

    <