算法解析-经典150（链表、二叉树）

链表

1.环形链表

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 141. 环形链表
 *
 * @Author sun
 * @Create 2024/12/24 13:37
 * @Version 1.0
 */
public class t141 {

    public boolean hasCycle(ListNode head) {
        // 快慢指针，慢的走一步，快的走两步，如果相遇就是有环
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

2.思路

快慢指针，慢的走一步，快的走两步，如果相遇就是有环

2.两数相加

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 2. 两数相加
 *
 * @Author sun
 * @Create 2024/12/24 13:44
 * @Version 1.0
 */
public class t2 {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode res = new ListNode(-1); // 哑节点
        ListNode index = res;
        int carry = 0; // 进位

        ListNode t1 = l1;
        ListNode t2 = l2;

        while (t1 != null || t2 != null) {
            // 获取当前节点的值，若为空则为0
            int val1 = (t1 != null) ? t1.val : 0;
            int val2 = (t2 != null) ? t2.val : 0;

            // 计算当前节点的和及进位
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            sum %= 10;

            // 添加当前节点
            res.next = new ListNode(sum);
            res = res.next;

            // 移动指针
            if (t1 != null) t1 = t1.next;
            if (t2 != null) t2 = t2.next;
        }

        // 检查是否还有未处理的进位
        if (carry > 0) {
            res.next = new ListNode(carry);
        }

        return index.next;
    }
}

2.思路

就是只要两个指针有一个不是null就可以获取节点值， 如果一个指针为空，那么节点值就是0，注意在计算和的时候需要加上上次的进位，并且还要计算当前进位以及和

3.合并两个有序链表

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 21. 合并两个有序链表
 *
 * @Author sun
 * @Create 2024/12/24 14:37
 * @Version 1.0
 */
public class t21 {

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // 哨兵节点
        ListNode dummy = new ListNode(-1);
        ListNode temp = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                temp.next = new ListNode(list1.val);
                temp = temp.next;
                list1 = list1.next;
            } else {
                temp.next = new ListNode(list2.val);
                temp = temp.next;
                list2 = list2.next;
            }
        }
        // 到这就表明有一个为null了
        temp.next = list1 == null ? list2 : list1;
        return dummy.next;
    }
}

2.思路

就是比较两个节点，谁小谁就放到结果后面，最后将剩余的整条链表接到结果后面即可

4.反转链表 II

1.答案

package com.sunxiansheng.classic150.g1;

import java.util.jar.JarEntry;

/**
 * Description: 92. 反转链表 II
 *
 * @Author sun
 * @Create 2024/12/25 09:10
 * @Version 1.0
 */
public class t92 {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 找到left的前一个节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        ListNode start = prev.next;
        ListNode then = start.next;
        for (int i = 0; i < right - left; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next;
    }
}

2.思路

要想反转链表，就要找到三个东西，prev，start，then，然后套公式，假如有三个节点就循环两次即可

5.反转链表

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 206. 反转链表
 *
 * @Author sun
 * @Create 2024/12/25 09:57
 * @Version 1.0
 */
public class t206 {

    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        // 三要素
        ListNode prev = dummy;
        ListNode start = head;
        ListNode then = head.next;
        // 套公式，假如五个节点需要循环四次！
        while (start.next != null) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next;
    }
}

2.思路

三要素：prev，start，then，套公式，假如五个节点需要循环四次！

6.K 个一组翻转链表

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 25. K 个一组翻转链表
 *
 * @Author sun
 * @Create 2024/12/25 10:04
 * @Version 1.0
 */
public class t25 {

    public ListNode reverseKGroup(ListNode head, int k) {
        // 创建哨兵节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;

        while (true) {
            // 检查是否有足够的节点可以反转
            ListNode temp = prev;
            int count = 0;
            while (temp.next != null) {
                count ++;
                temp = temp.next;
            }
            // 只要没有足够的节点，就break
            if (count < k) {
                break;
            }
            // 到这里就可以反转一组链表了
            ListNode start = prev.next;
            ListNode then = start.next;
            reverse(prev, start, then, k);
            // 反转之后更新prev
            prev = start;
        }
        return dummy.next;
    }

    /**
     * 反转一组链表
     *
     * @param prev
     * @param start
     * @param then
     */
    private void reverse(ListNode prev, ListNode start, ListNode then, int k) {
        for (int i = 0; i < k - 1; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
    }
}

2.思路

首先要知道反转一组链表就是标准公式执行k-1次，然后要知道反转完链表之后的指针状态

1：prev

2：start

3：then

4

反转一次后，prev不变，start和then向后移动一位

1：prev

2

3：start

4：then

这样在反转完一组链表之后，更新prev=start即可

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

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 19. 删除链表的倒数第 N 个结点
 *
 * @Author sun
 * @Create 2024/12/25 13:10
 * @Version 1.0
 */
public class t19 {

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        getNodeNum(dummy, n);
        return dummy.next;
    }

    public static int getNodeNum(ListNode node, int n) {
        if (node.next == null) {
            // 倒数第一个节点
            return 1;
        } else {
            int nodeNum = getNodeNum(node.next, n);
            // 如果这个节点数就是要删除的就进行删除
            if (n == nodeNum) {
                if (n == 1) {
                    node.next = null;
                } else {
                    node.next = node.next.next;
                }
            }
            return nodeNum + 1;
        }
    }
}

2.思路

使用递归来完成，递归从最后一个节点开始计数，也就是返回当前节点是倒数第几个节点，然后进行删除操作即可

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

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 82. 删除排序链表中的重复元素 II
 *
 * @Author sun
 * @Create 2024/12/25 13:21
 * @Version 1.0
 */
public class t82 {

    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode temp = dummy;
        while (temp.next != null) {
            ListNode right = temp.next;
            // 首先判断当前元素是不是重复元素
            if (right.next != null && right.val == right.next.val) {
                // 如果是重复元素，就将right移动到不重复的元素的位置
                while (right.next != null && right.val == right.next.val) {
                    right = right.next;
                }
                right = right.next;
                // 删除重复元素
                temp.next = right;
                // 然后temp就不用变了
            } else {
                // 如果不重复，那么temp正常移动
                temp = temp.next;
            }
        }
        return dummy.next;
    }
}

2.思路

使用虚拟节点进行正常遍历，首先判断当前元素是不是重复元素，如果是，就使用while移动到重复元素的最后一个元素的位置，并且再向后移动一个，让temp指向这个指针实现删除操作

9.旋转链表

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 61. 旋转链表
 *
 * @Author sun
 * @Create 2024/12/25 13:47
 * @Version 1.0
 */
public class t61 {

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode[] find = new ListNode[1];
        ListNode dummy = new ListNode(-10);
        dummy.next = head;

        // 统计链表元素个数
        ListNode temp = dummy;
        int count = 0;
        while (temp.next != null) {
            count++;
            temp = temp.next;
        }

        if (k % count == 0) {
            return head;
        }

        findNode(dummy, k % count, find, dummy);
        return find[0];
    }

    /**
     * 找到倒数第k个节点，然后让倒数第k-1个节点指向null，并且让最后一个节点的next指向第一个节点
     *
     * @param node
     * @param k
     * @param find
     */
    public static int findNode(ListNode node, int k, ListNode[] find, ListNode dummy) {
        if (node.next == null) {
            node.next = dummy.next;
            return 1;
        } else {
            int nodeNum = findNode(node.next, k, find, dummy);
            // 表明当前节点的后一个节点是倒数第k个节点
            if (nodeNum == k) {
                // 记录节点
                find[0] = node.next;
                // 让当前节点指向null
                node.next = null;
            }
            return nodeNum + 1;
        }
    }
}

2.思路

递归找到倒数第k-1个节点，让他的next指向null，并且找到最后一个节点，让他的next指向第一个节点

10.分隔链表

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 86. 分隔链表
 *
 * @Author sun
 * @Create 2024/12/25 14:21
 * @Version 1.0
 */
public class t86 {

    public ListNode partition(ListNode head, int x) {
        // 两个链表，一个链表存储小于等于x的节点，另一个链表存储大于等于x的节点
        ListNode small = new ListNode(-1);
        ListNode big = new ListNode(-1);
        ListNode s = small;
        ListNode b = big;
        // 遍历链表
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode temp = dummy;
        while (temp.next != null) {
            // 取出当前元素
            ListNode cur = temp.next;
            if (cur.val < x) {
                s.next = cur;
                s = s.next;
            } else {
                b.next = cur;
                b = b.next;
            }
            temp = temp.next;
        }
        // 注意需要让大的节点的next为null
        b.next = null;
        // 拼接链表
        s.next = big.next;
        return small.next;
    }
}

2.思路

使用两个链表，一个存小于x的元素，另一个存大于等于x的元素，最后拼接链表即可

11.LRU 缓存

1.答案

package com.sunxiansheng.classic150.g1;

import java.util.HashMap;
import java.util.Map;

/**
 * Description: 146. LRU 缓存
 *
 * @Author sun
 * @Create 2024/12/25 14:47
 * @Version 1.1
 */
public class LRUCache {

    /**
     * 节点
     */
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
        }

        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用头结点和尾节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    /**
     * 获取值
     */
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 移动到头部
        moveToHead(node);
        return node.value;
    }

    /**
     * 插入或更新值
     */
    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果不存在，新建节点
            DLinkedNode newNode = new DLinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            size++;
            // 超出容量，移除尾部节点
            if (size > capacity) {
                DLinkedNode tailNode = removeTail();
                cache.remove(tailNode.key);
                size--;
            }
        } else {
            // 如果存在，更新值并移动到头部
            node.value = value;
            moveToHead(node);
        }
    }

    /**
     * 添加节点到头部
     */
    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    /**
     * 移除节点
     */
    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * 移动节点到头部
     */
    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 移除尾部节点
     */
    private DLinkedNode removeTail() {
        DLinkedNode tailNode = tail.prev;
        removeNode(tailNode);
        return tailNode;
    }
}

2.思路

LRU缓存由双向链表和缓存的Map来实现

双向链表有四个参数：key，value，prev，next

Map的key是key，value是双向链表的节点

整体缓存的属性有Map，head，tail，大小和容量

注意首先实现四个方法，分别是从双向链表中删除元素，添加元素到头部，移动元素到头部，删除尾部节点

二叉树

1.二叉树的最大深度

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 104. 二叉树的最大深度
 *
 * @Author sun
 * @Create 2024/12/26 10:13
 * @Version 1.0
 */
public class t104 {

    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            // 左右子树的最大深度加1，就是当前子树的最大深度
            return Math.max(left, right) + 1;
        }
    }
}

2.思路

左右子树的最大深度加1，就是当前子树的最大深度

2.相同的树

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 100. 相同的树
 *
 * @Author sun
 * @Create 2024/12/26 10:23
 * @Version 1.0
 */
public class t100 {

    public static boolean isSameTree(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else {
            // 首先比较当前两个节点是不是相同，
            if (left.val != right.val) {
                return false;
            }
            boolean leftTree = isSameTree(left.left, right.left);
            boolean rightTree = isSameTree(left.right, right.right);
            // 左右子树都要是相同的才可以
            return leftTree && rightTree;
        }
    }
}

2.思路

确认递归函数定义，参数传递状态，确认终止条件，对返回值进行处理

3.翻转二叉树

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 226. 翻转二叉树
 *
 * @Author sun
 * @Create 2024/12/26 10:37
 * @Version 1.0
 */
public class t226 {

    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        } else {
            TreeNode left = invertTree(root.left);
            TreeNode right = invertTree(root.right);
            // 反转左右子树
            root.left = right;
            root.right = left;
            return root;
        }
    }
}

2.思路

从底向下， 反转左右子树

4.对称二叉树

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 101. 对称二叉树
 *
 * @Author sun
 * @Create 2024/12/26 10:42
 * @Version 1.0
 */
public class t101 {

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return check(root.left, root.right);
    }

    // 检查左右子树是否是对称的
    public static boolean check(TreeNode left, TreeNode right) {
        if (left == null && right == null) {
            return true;
        } else if (left == null || right == null) {
            return false;
        } else {
            if (left.val != right.val) {
                return false;
            }
            boolean leftTree = check(left.right, right.left);
            boolean rightTree = check(right.right, left.left);
            return leftTree && rightTree;
        }
    }
}

2.思路

跟相同的树的思路类似的，不过需要单独写一个递归函数来检查左右子树是否对称

5.填充每个节点的下一个右侧节点指针 II

1.答案

package com.sunxiansheng.classic150.g1;

import javax.swing.*;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Description: 117. 填充每个节点的下一个右侧节点指针 II
 *
 * @Author sun
 * @Create 2024/12/26 10:52
 * @Version 1.0
 */
public class t117 {

    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

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

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

    public Node connect(Node root) {
        if (root == null) {
            return null;
        }
        // 队列
        Queue<Node> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 当前层的节点数
            int size = queue.size();
            // 前一个节点
            Node prev = null;
            // 遍历当前层节点
            for (int i = 0; i < size; i++) {
                // 取出当前节点
                Node node = queue.poll();
                if (prev == null) {
                    prev = node;
                } else {
                    prev.next = node;
                    prev = node;
                }
                // 左右节点入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return root;
    }
}

2.思路

层序遍历即可，记录前一个节点，让前一个节点的next指向当前节点

6.二叉树展开为链表

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 114. 二叉树展开为链表
 *
 * @Author sun
 * @Create 2024/12/26 11:04
 * @Version 1.0
 */
public class t114 {

    TreeNode prev;

    // 反前序遍历
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        } else {
            flatten(root.right);
            flatten(root.left);
            root.left = null;
            root.right = prev;
            prev = root;
        }
    }
}

2.思路

反前序遍历

7.路径总和

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 112. 路径总和
 *
 * @Author sun
 * @Create 2024/12/26 12:18
 * @Version 1.0
 */
public class t112 {

    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        int[] cur = new int[2];
        backtrace(root, targetSum, cur);
        return cur[1] == 10000;
    }

    public static void backtrace(TreeNode root, int targetSum, int[] curSum) {
        if (root.left == null && root.right == null) {
            // 计算和
            curSum[0] += root.val;
            // 判断是否是结果
            if (curSum[0] == targetSum) {
                // 使用curSum[1]作为标记
                curSum[1] = 10000;
            }
            // 回溯
            curSum[0] -= root.val;
        } else {
            // 计算和
            curSum[0] += root.val;
            // 传递状态
            if (root.left != null) {
                backtrace(root.left, targetSum, curSum);
            }
            if (root.right != null) {
                backtrace(root.right, targetSum, curSum);
            }
            // 回溯
            curSum[0] -= root.val;
        }
    }
}

2.思路

用到了回溯法，核心就是参数记录路径，传递参数 ，当遇到叶子节点时计算结果并回溯

8.求根节点到叶节点数字之和

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 129. 求根节点到叶节点数字之和
 *
 * @Author sun
 * @Create 2024/12/26 12:40
 * @Version 1.0
 */
public class t129 {

    public int sumNumbers(TreeNode root) {
        int[] sum = new int[1];
        backtrace(root, new StringBuilder(), sum);
        return sum[0];
    }

    public static void backtrace(TreeNode root, StringBuilder path, int[] sum) {
        if (root.right == null && root.left == null) {
            // 叶子节点
            // 记录路径
            path.append(root.val);
            // 计算结果
            sum[0] += Integer.parseInt(path.toString());
            // 回溯
            path.deleteCharAt(path.length() - 1);
        } else {
            // 记录路径
            path.append(root.val);
            // 传递状态
            if (root.left != null) {
                backtrace(root.left, path, sum);
            }
            if (root.right != null) {
                backtrace(root.right, path, sum);
            }
            // 回溯
            path.deleteCharAt(path.length() - 1);
        }
    }
}

2.思路

就是回溯老套路了

9.二叉搜索树迭代器

1.答案

package com.sunxiansheng.classic150.g1;

import java.util.ArrayList;
import java.util.List;

/**
 * Description: 173. 二叉搜索树迭代器
 *
 * @Author sun
 * @Create 2024/12/26 12:56
 * @Version 1.0
 */
public class BSTIterator {

    private List<Integer> arr;

    private int idx;

    public BSTIterator(TreeNode root) {
        idx = 0;
        arr = new ArrayList<>();
        middleOrder(root);
    }

    public int next() {
        return arr.get(idx++);
    }

    public boolean hasNext() {
        return idx < arr.size();
    }

    // 中序遍历，将结果放到数组中
    public void middleOrder(TreeNode root) {
        if (root == null) {
            return;
        } else {
            middleOrder(root.left);
            arr.add(root.val);
            middleOrder(root.right);
        }
    }
}

2.思路

就是先中序遍历到数组里面，然后根据方法的意思来编写迭代器即可

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

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 222. 完全二叉树的节点个数
 *
 * @Author sun
 * @Create 2024/12/27 08:35
 * @Version 1.0
 */
public class t222 {

    public int countNodes(TreeNode root) {
        int[] res = new int[1];
        count(root, res);
        return res[0];
    }

    private void count(TreeNode root, int[] res) {
        if (root == null) {
            return;
        } else {
            res[0]++;
            count(root.left, res);
            count(root.right, res);
        }
    }
}

2.思路

遍历一下统计数量即可

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

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 236. 二叉树的最近公共祖先
 *
 * @Author sun
 * @Create 2024/12/27 08:53
 * @Version 1.0
 */
public class t236 {

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        } else if (root == p || root == q){
            return root;
        } else {
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            // 都为空，则当前子树的公共祖先就是null
            if (left == null && right == null) {
                return null;
            }
            // 一个为空，一个不为空，返回不为空的
            if (left == null || right == null) {
                return left == null ? right : left;
            }
            // 如果两个都不为空，则当前节点就是公共祖先
            return root;
        }
    }
}

2.思路

首先对递归函数进行定义，返回根节点为root的树对于节点p和q的公共祖先，然后对终止条件进行处理，如果根节点为空，那么公共祖先就为空，如果根节点为p或者q，就直接返回p或者q，最后对else进行处理，如果左右子树都返回空，就返回空，一个为空，一个不为空，就返回不为空的，两个都不为空，则当前节点就是公共祖先

12.二叉树的右视图

1.答案

package com.sunxiansheng.classic150.g1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Description: 199. 二叉树的右视图
 *
 * @Author sun
 * @Create 2024/12/27 09:22
 * @Version 1.0
 */
public class t199 {

    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 size = queue.size();
            // 遍历当前层的节点
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                // 只要最后一个元素
                if (i == size - 1) {
                    res.add(node.val);
                }
                // 左右子树
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return res;
    }
}

2.思路

层序遍历即可

13.二叉树的层平均值

1.答案

package com.sunxiansheng.classic150.g1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Description: 637. 二叉树的层平均值
 *
 * @Author sun
 * @Create 2024/12/27 09:33
 * @Version 1.0
 */
public class t637 {

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            double 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);
                }
            }
            res.add(sum / n);
        }
        return res;
    }
}

2.思路

简单的层序遍历

14.二叉树的层序遍历

1.答案

package com.sunxiansheng.classic150.g1;

import com.sun.org.apache.bcel.internal.generic.NOP;

import javax.annotation.Resource;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Description: 102. 二叉树的层序遍历
 *
 * @Author sun
 * @Create 2024/12/27 09:38
 * @Version 1.0
 */
public class t102 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 当前层的节点数
            int size = queue.size();
            // 当前层的节点
            List<Integer> list = new ArrayList<>();
            // 遍历当前层的节点
            for (int i = 0; i < size; i++) {
                // 取出当前节点
                TreeNode node = queue.poll();
                list.add(node.val);
                // 左右节点入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 加入到结果
            res.add(list);
        }
        return res;
    }
}

2.思路

基本层序遍历

15.二叉树的锯齿形层序遍历

1.答案

package com.sunxiansheng.classic150.g1;

import com.sun.org.apache.bcel.internal.generic.NOP;

import javax.annotation.Resource;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Description: 103. 二叉树的锯齿形层序遍历
 *
 * @Author sun
 * @Create 2024/12/27 09:38
 * @Version 1.0
 */
public class t103 {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队
        queue.offer(root);
        // 是否向右遍历
        boolean toRight = true;
        while (!queue.isEmpty()) {
            // 当前层的节点数
            int size = queue.size();
            // 当前层的节点
            LinkedList<Integer> list = new LinkedList<>();
            // 遍历当前层的节点
            for (int i = 0; i < size; i++) {
                // 取出当前节点
                TreeNode node = queue.poll();
                // 根据标志来决定是添加到链表的头部还是尾部
                if (toRight) {
                    list.addLast(node.val);
                } else {
                    list.addFirst(node.val);
                }
                // 左右节点入队
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 加入到结果
            res.add(list);
            // 更改方向
            toRight = !toRight;
        }
        return res;
    }
}

2.思路

根据方向标识决定是添加到链表的头部还是尾部

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

1.答案

package com.sunxiansheng.classic150.g1;

import java.nio.file.Path;

/**
 * Description: 530. 二叉搜索树的最小绝对差
 *
 * @Author sun
 * @Create 2024/12/27 09:50
 * @Version 1.0
 */
public class t530 {

    public int getMinimumDifference(TreeNode root) {
        // 核心，二叉搜索树的中序遍历是升序，那么最小差值一定是相邻的两个节点的差值
        int[] res = new int[2];
        res[0] = Integer.MAX_VALUE;
        // res[1]就是prev
        res[1] = -1;
        middleOrder(root, res);
        return res[0];
    }

    public static void middleOrder(TreeNode root, int[] res) {
        if (root == null) {
            return;
        } else {
            middleOrder(root.left, res);
            // root即为当前节点
            if (res[1] == -1) {
                res[1] = root.val;
            } else {
                // 计算差值并更新prev
                res[0] = Math.min(res[0], root.val - res[1]);
                res[1] = root.val;
            }
            middleOrder(root.right, res);
        }
    }
}

2.思路

利用二叉搜索树的中序遍历是升序这个特性来做即可，记录一下prev，求相邻两个节点的差值并记录最小差值

17.二叉搜索树中第 K 小的元素

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 230. 二叉搜索树中第 K 小的元素
 *
 * @Author sun
 * @Create 2024/12/27 10:26
 * @Version 1.0
 */
public class t230 {

    public int kthSmallest(TreeNode node, int k) {
        int[] res = new int[2];
        // res[0]是第k小的元素，res[1]是第几个元素
        middleOrder(node, k, res);
        return res[0];
    }

    public static void middleOrder(TreeNode root, int k, int[] res) {
        if (root == null) {
            return;
        } else {
            middleOrder(root.left, k, res);
            // root即为当前元素
            // 如果当前是第k个元素，记录结果直接return
            if (++res[1] == k) {
                res[0] = root.val;
                return;
            }
            middleOrder(root.right, k, res);
        }
    }
}

2.思路

利用二叉搜索树的中序遍历是升序这个特性来做即可

17.验证二叉搜索树

1.答案

package com.sunxiansheng.classic150.g1;

/**
 * Description: 98. 验证二叉搜索树
 *
 * @Author sun
 * @Create 2024/12/27 10:33
 * @Version 1.0
 */
public class t98 {

    public boolean isValidBST(TreeNode root) {
        Integer[] res = new Integer[2];
        // res[0]如果是null，则是二叉搜索树，res[1]存的是前一个节点的值
        middleOrder(root, res);
        return res[0] == null;
    }

    private void middleOrder(TreeNode root, Integer[] res) {
        if (root == null) {
            return;
        } else {
            middleOrder(root.left, res);
            if (res[1] == null) {
                res[1] = root.val;
            } else {
                // 判断是否满足要求
                if (!(root.val > res[1])) {
                    res[0] = 1;
                    return;
                }
                // 更新prev
                res[1] = root.val;
            }
            middleOrder(root.right, res);
        }
    }
}

2.思路

利用二叉搜索树的中序遍历是升序这个特性来做即可，直接中序遍历，在根做处理