13-算法与数据结构

// Java Arrays.sort() 对基本类型用快速排序，对对象用TimSort（归并）
int[] arr = {5, 1, 3, 2, 4};
Arrays.sort(arr); // 基本类型：双轴快速排序

List<Integer> list = Arrays.asList(5, 1, 3, 2, 4);
Collections.sort(list); // 对象：TimSort（稳定归并）

// 手动选择排序
// 数据近乎有序 → 插入排序 O(n)
// 大规模数据 → 快速排序 / 归并排序
// 需稳定排序 → 归并排序 / 计数排序
// 空间受限 → 堆排序 / 快速排序

循环条件: left <= right
  mid = left + (right - left) / 2   // 防溢出
  如果 arr[mid] == target → 找到
  如果 arr[mid] < target  → left = mid + 1（去右半部分）
  如果 arr[mid] > target  → right = mid - 1（去左半部分）
循环结束: 未找到

循环条件: left < right
  mid = left + (right - left) / 2   // 向下取整
  如果 arr[mid] < target  → left = mid + 1
  否则                    → right = mid
循环结束: left == right == 左边界

循环条件: left < right
  mid = left + (right - left + 1) / 2   // 向上取整
  如果 arr[mid] > target  → right = mid - 1
  否则                     → left = mid
循环结束: left == right == 右边界

// 标准二分查找
public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// 搜索左边界（第一个 >= target 的位置）
public static int searchLeftBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

// 搜索右边界（最后一个 <= target 的位置）
public static int searchRightBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left + 1) / 2;
        if (arr[mid] > target) right = mid - 1;
        else left = mid;
    }
    return left;
}

// 示例：0-1 背包问题
// 物品重量 w[], 价值 v[], 背包容量 C
// 求最大价值

public static int knapsack(int[] w, int[] v, int C) {
    int n = w.length;
    int[] dp = new int[C + 1]; // dp[j] 表示容量为 j 时的最大价值

    for (int i = 0; i < n; i++) {
        for (int j = C; j >= w[i]; j--) { // 逆序遍历保证每个物品只用一次
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[C];
}

// 示例：最长递增子序列 (LIS)
public static int lengthOfLIS(int[] nums) {
    int[] dp = new int[nums.length]; // dp[i] 以 nums[i] 结尾的LIS长度
    Arrays.fill(dp, 1);             // 每个元素自身构成长度为1的子序列

    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLen = 0;
    for (int len : dp) maxLen = Math.max(maxLen, len);
    return maxLen;
}

void backtrack(路径, 选择列表):
    if 终止条件:
        记录解 / 返回

    for 选择 in 选择列表:
        if 剪枝条件: continue
        做选择 (路径.add, 标记已使用)
        backtrack(新路径, 新选择列表)
        撤销选择 (路径.remove, 恢复未使用)

在 n×n 棋盘上放置 n 个皇后，每行一个，互不攻击。

决策树深度: n（每行放一个皇后）
每层选择: n 列
剪枝: 同列、同对角线冲突

// 示例：全排列
public static List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
    return result;
}

private static void backtrack(int[] nums, boolean[] used,
                               List<Integer> path, List<List<Integer>> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;       // 剪枝：已使用的元素不再选
        path.add(nums[i]);            // 做选择
        used[i] = true;
        backtrack(nums, used, path, result);
        used[i] = false;              // 撤销选择
        path.remove(path.size() - 1);
    }
}

// 示例：N皇后
public static List<List<String>> solveNQueens(int n) {
    List<List<String>> result = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrackQueen(board, 0, result);
    return result;
}

private static void backtrackQueen(char[][] board, int row,
                                    List<List<String>> result) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isValidQueen(board, row, col)) { // 剪枝
            board[row][col] = 'Q';           // 做选择
            backtrackQueen(board, row + 1, result);
            board[row][col] = '.';            // 撤销选择
        }
    }
}

// 示例：区间调度（最多不重叠区间数）
public static int maxNonOverlappingIntervals(int[][] intervals) {
    // Step 1: 按结束时间排序
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

    int count = 1;
    int end = intervals[0][1];

    // Step 2: 贪心选择下一个不重叠且最早结束的
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }
    return count;
}

// 示例：Huffman 编码
public static Map<Character, String> huffmanEncode(Map<Character, Integer> freq) {
    PriorityQueue<HuffNode> pq = new PriorityQueue<>();
    for (var entry : freq.entrySet()) {
        pq.offer(new HuffNode(entry.getKey(), entry.getValue()));
    }

    while (pq.size() > 1) {
        HuffNode left = pq.poll();
        HuffNode right = pq.poll();
        pq.offer(new HuffNode(null, left.weight + right.weight, left, right));
    }
    // 生成编码...
}

1. 初始化：queue = [start], visited = {start}
2. While queue 非空:
     node = queue.poll()
     访问 node
     for neighbor in node 的邻居:
       if neighbor 未访问:
         visited.add(neighbor)
         queue.offer(neighbor)

1. 访问 node, 标记已访问
2. for neighbor in node 的邻居:
     if neighbor 未访问:
       DFS(neighbor)

// BFS 示例：二叉树层次遍历
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; 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);
        }
        result.add(level);
    }
    return result;
}

// DFS 示例：二叉树前序遍历（递归）
public static List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    dfsPreorder(root, result);
    return result;
}

private static void dfsPreorder(TreeNode node, List<Integer> result) {
    if (node == null) return;
    result.add(node.val);          // 访问根
    dfsPreorder(node.left, result);  // 遍历左
    dfsPreorder(node.right, result); // 遍历右
}

// DFS 示例：迭代式（栈实现）
public static List<Integer> preorderIterative(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        result.add(node.val);
        if (node.right != null) stack.push(node.right);  // 先压右
        if (node.left != null) stack.push(node.left);    // 再压左（先出）
    }
    return result;
}

public static void heapSort(int[] arr) {
    int n = arr.length;

    // Step 1: 建大顶堆（自底向上）
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Step 2: 依次取堆顶放到末尾
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);    // 最大值移到末尾
        heapify(arr, i, 0);  // 对剩余元素重新堆化
    }
}

private static void heapify(int[] arr, int heapSize, int root) {
    int largest = root;
    int left = 2 * root + 1;
    int right = 2 * root + 2;

    if (left < heapSize && arr[left] > arr[largest]) largest = left;
    if (right < heapSize && arr[right] > arr[largest]) largest = right;

    if (largest != root) {
        swap(arr, root, largest);
        heapify(arr, heapSize, largest); // 递归调整
    }
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}

选择 pivot = arr[high]
i = low - 1
for j = low to high - 1:
    if arr[j] <= pivot:
        i++
        swap arr[i], arr[j]
swap arr[i+1], arr[high]
返回 i+1 (pivot 最终位置)

选择 pivot = arr[low]
i = low + 1, j = high
循环:
    while i <= high and arr[i] < pivot: i++
    while j > low and arr[j] > pivot: j--
    if i < j: swap arr[i], arr[j]
    else: break
swap arr[low], arr[j]
返回 j

public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static void quickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    if (high - low < 16) {
        insertionSort(arr, low, high); // 小区间用插入排序优化
        return;
    }

    int pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
}

private static int partition(int[] arr, int low, int high) {
    // 三数取中选择基准
    int mid = low + (high - low) / 2;
    if (arr[low] > arr[high]) swap(arr, low, high);
    if (arr[mid] > arr[high]) swap(arr, mid, high);
    if (arr[mid] > arr[low]) swap(arr, mid, low);
    // 基准放到 high-1 位置
    swap(arr, mid, high);

    int pivot = arr[high];
    int i = low;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            swap(arr, i++, j);
        }
    }
    swap(arr, i, high);
    return i;
}

private static void insertionSort(int[] arr, int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;
}

public static void mergeSort(int[] arr) {
    int[] temp = new int[arr.length];
    mergeSort(arr, 0, arr.length - 1, temp);
}

private static void mergeSort(int[] arr, int left, int right, int[] temp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid, temp);
    mergeSort(arr, mid + 1, right, temp);
    merge(arr, left, mid, right, temp);
}

private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int i = left, j = mid + 1, k = left;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++]; // 注意：<= 保证稳定性
        } else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int idx = left; idx <= right; idx++) {
        arr[idx] = temp[idx];
    }
}

prev = null, curr = head
while curr != null:
    nextTemp = curr.next   // 保存下一个节点
    curr.next = prev       // 反转指针
    prev = curr            // prev 前移
    curr = nextTemp        // curr 前移
return prev

reverseList(head):
    if head == null or head.next == null: return head
    newHead = reverseList(head.next)  // 先递归到尾部
    head.next.next = head              // 反转指针
    head.next = null                   // 断开原指针
    return newHead

// 单链表整体反转 - 迭代
public static ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode nextTemp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

// 单链表整体反转 - 递归
public static ListNode reverseListRecursive(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

// K个一组翻转
public static ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;

    while (pre.next != null) {
        // 找到每组的尾节点
        ListNode end = pre;
        for (int i = 0; i < k && end != null; i++) end = end.next;
        if (end == null) break; // 不足一组

        ListNode start = pre.next;
        ListNode nextGroup = end.next; // 保存下一组起点

        // 反转本组
        end.next = null;
        pre.next = reverseList(start);
        start.next = nextGroup;

        pre = start; // pre 移到本组的尾（反转后的尾）
    }
    return dummy.next;
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
}

curr = head
while curr != null:
    swap curr.prev and curr.next
    curr = curr.prev  (注意：交换后 prev 是原 next)
return newHead (原尾节点)

public static DoublyListNode reverseDoublyList(DoublyListNode head) {
    DoublyListNode curr = head;
    DoublyListNode newHead = null;

    while (curr != null) {
        // 交换 prev 和 next
        DoublyListNode temp = curr.prev;
        curr.prev = curr.next;
        curr.next = temp;

        // 下一个节点是交换后的 prev（即原 next）
        newHead = curr;
        curr = curr.prev;
    }

    return newHead; // 原尾节点成为新头节点
}

// 更简洁的写法
public static DoublyListNode reverseDoublyListV2(DoublyListNode head) {
    DoublyListNode curr = head;
    while (curr != null) {
        DoublyListNode next = curr.next;
        curr.next = curr.prev;
        curr.prev = next;
        if (curr.prev == null) head = curr;
        curr = curr.prev;
    }
    return head;
}

class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
    DoublyListNode(int val) { this.val = val; }
}

import java.util.Stack;
import java.util.concurrent.locks.ReentrantLock;

public class MyQueue<T> {
    private final Stack<T> inStack = new Stack<>();
    private final Stack<T> outStack = new Stack<>();
    private final ReentrantLock lock = new ReentrantLock();

    // 入队
    public void push(T x) {
        lock.lock();
        try {
            inStack.push(x);
        } finally {
            lock.unlock();
        }
    }

    // 出队
    public T pop() {
        lock.lock();
        try {
            if (outStack.isEmpty()) {
                while (!inStack.isEmpty()) {
                    outStack.push(inStack.pop());
                }
            }
            return outStack.pop();
        } finally {
            lock.unlock();
        }
    }

    // 查看队首
    public T peek() {
        lock.lock();
        try {
            if (outStack.isEmpty()) {
                while (!inStack.isEmpty()) {
                    outStack.push(inStack.pop());
                }
            }
            return outStack.peek();
        } finally {
            lock.unlock();
        }
    }

    // 是否为空
    public boolean empty() {
        lock.lock();
        try {
            return inStack.isEmpty() && outStack.isEmpty();
        } finally {
            lock.unlock();
        }
    }
}

import java.util.HashMap;

public class LRUCache {
    static class Node {
        int key, value;
        Node prev, next;
        Node(int k, int v) { key = k; value = v; }
    }

    private final int capacity;
    private final HashMap<Integer, Node> map;
    private final Node head, tail; // 伪头和伪尾

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(-1, -1); // 伪头
        this.tail = new Node(-1, -1); // 伪尾
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);

            if (map.size() > capacity) {
                Node tailNode = removeTail();
                map.remove(tailNode.key);
            }
        }
    }

    private void addToHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
}

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCacheJava {
    private final LinkedHashMap<Integer, Integer> cache;
    private final int capacity;

    public LRUCacheJava(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<>(16, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        cache.put(key, value);
    }
}

三个指针:
  p1 = m - 1 (nums1 的有效末尾)
  p2 = n - 1 (nums2 的末尾)
  p = m + n - 1 (nums1 的填充末尾)

循环:
    if p1 >= 0 and (p2 < 0 or nums1[p1] > nums2[p2]):
        nums1[p] = nums1[p1]
        p1--
    else:
        nums1[p] = nums2[p2]
        p2--
    p--

public static void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1;
    int p2 = n - 1;
    int p = m + n - 1;

    while (p1 >= 0 || p2 >= 0) {
        if (p1 >= 0 && (p2 < 0 || nums1[p1] > nums2[p2])) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }
}

// 合并两个有序数组到新数组
public static int[] mergeToNew(int[] a, int[] b) {
    int[] result = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length) {
        if (a[i] <= b[j]) {
            result[k++] = a[i++];
        } else {
            result[k++] = b[j++];
        }
    }

    while (i < a.length) result[k++] = a[i++];
    while (j < b.length) result[k++] = b[j++];

    return result;
}

public static int[] searchRange(int[] nums, int target) {
    int left = findBound(nums, target, true);
    int right = findBound(nums, target, false);
    return new int[]{left, right};
}

// isLeft: true 找左边界，false 找右边界
private static int findBound(int[] nums, int target, boolean isLeft) {
    int left = 0, right = nums.length;

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            if (isLeft) {
                right = mid;   // 收缩右边界
            } else {
                left = mid + 1; // 收缩左边界（注意这里）
            }
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    // 左边界判断找到与否
    if (isLeft) {
        if (left == nums.length || nums[left] != target) return -1;
        return left;
    } else {
        if (left == 0 || nums[left - 1] != target) return -1;
        return left - 1; // 右边界是 left - 1
    }
}

// 更简洁的写法
public static int[] searchRangeSimpler(int[] nums, int target) {
    int leftBound = findLeft(nums, target);
    if (leftBound >= nums.length || nums[leftBound] != target) {
        return new int[]{-1, -1};
    }
    int rightBound = findRight(nums, target);
    return new int[]{leftBound, rightBound};
}

private static int findLeft(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;
    }
    return left;
}

private static int findRight(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left + 1) / 2; // 向上取整
        if (nums[mid] <= target) left = mid;
        else right = mid - 1;
    }
    return left;
}

public static int countDigitOne(int n) {
    int count = 0;
    long factor = 1; // 当前位基数：1, 10, 100, ...

    while (n >= factor) {
        long higher = n / (factor * 10); // 高位
        long curr = (n / factor) % 10;    // 当前位
        long lower = n % factor;          // 低位

        // 当前位为1时的贡献
        long contrib;
        if (curr == 0) {
            contrib = higher * factor;
        } else if (curr == 1) {
            contrib = higher * factor + lower + 1;
        } else {
            contrib = (higher + 1) * factor;
        }

        count += contrib;
        factor *= 10;
    }

    return count;
}

candies[0] = 1
for i = 1 to n-1:
    if ratings[i] > ratings[i-1]:
        candies[i] = candies[i-1] + 1
    else:
        candies[i] = 1

for i = n-2 to 0:
    if ratings[i] > ratings[i+1]:
        candies[i] = max(candies[i], candies[i+1] + 1)

public static int candy(int[] ratings) {
    int n = ratings.length;
    if (n == 0) return 0;

    int[] candies = new int[n];
    Arrays.fill(candies, 1); // 每个孩子至少 1 颗

    // 左→右
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }

    // 右→左
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }

    int total = 0;
    for (int c : candies) total += c;
    return total;
}

// 空间 O(1) 优化版（上坡+下坡计数）
public static int candyO1(int[] ratings) {
    int n = ratings.length;
    if (n <= 1) return n;

    int total = 1;
    int up = 1, down = 0, peak = 1;

    for (int i = 1; i < n; i++) {
        if (ratings[i] >= ratings[i - 1]) {
            up++;
            peak = up;
            down = 0;
            total += up;
        } else {
            down++;
            up = 1;
            total += down;
            if (down >= peak) total++;
        }
    }
    return total;
}

buildTree(nums, left, right):
    if left > right: return null
    mid = left + (right - left) / 2
    root = new TreeNode(nums[mid])
    root.left = buildTree(nums, left, mid - 1)
    root.right = buildTree(nums, mid + 1, right)
    return root

public static TreeNode sortedArrayToBST(int[] nums) {
    return buildTree(nums, 0, nums.length - 1);
}

private static TreeNode buildTree(int[] nums, int left, int right) {
    if (left > right) return null;

    int mid = left + (right - left) / 2;
    TreeNode root = new TreeNode(nums[mid]);

    root.left = buildTree(nums, left, mid - 1);
    root.right = buildTree(nums, mid + 1, right);

    return root;
}

// 迭代式（层序构造）
public static TreeNode sortedArrayToBSTIterative(int[] nums) {
    if (nums.length == 0) return null;

    TreeNode root = new TreeNode(0); // 占位
    Queue<Object[]> queue = new LinkedList<>();
    queue.offer(new Object[]{root, 0, nums.length - 1});

    while (!queue.isEmpty()) {
        Object[] obj = queue.poll();
        TreeNode node = (TreeNode) obj[0];
        int left = (int) obj[1];
        int right = (int) obj[2];

        int mid = left + (right - left) / 2;
        node.val = nums[mid]; // 设置根节点值

        if (left <= mid - 1) {
            node.left = new TreeNode(0);
            queue.offer(new Object[]{node.left, left, mid - 1});
        }
        if (mid + 1 <= right) {
            node.right = new TreeNode(0);
            queue.offer(new Object[]{node.right, mid + 1, right});
        }
    }
    return root;
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

queue = [root]
while queue 非空:
    levelSize = queue.size()
    level = []
    for i = 0 to levelSize - 1:
        node = queue.poll()
        level.add(node.val)
        if node.left: queue.offer(node.left)
        if node.right: queue.offer(node.right)
    result.add(level)

// 标准层次遍历
public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        List<Integer> level = new ArrayList<>();

        for (int i = 0; i < levelSize; 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);
        }
        result.add(level);
    }
    return result;
}

// Z 字形遍历
public static List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean leftToRight = true;

    while (!queue.isEmpty()) {
        int size = queue.size();
        LinkedList<Integer> level = new LinkedList<>();

        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            if (leftToRight) {
                level.addLast(node.val);
            } else {
                level.addFirst(node.val);
            }

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        result.add(level);
        leftToRight = !leftToRight;
    }
    return result;
}

// 二叉树右视图
public static List<Integer> rightSideView(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) return result;

    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) result.add(node.val);

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
    return result;
}

// 二叉树最大宽度
public static int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int maxWidth = 0;
    Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
    queue.offer(new Pair<>(root, 0));

    while (!queue.isEmpty()) {
        int size = queue.size();
        int leftmost = queue.peek().getValue();
        int rightmost = leftmost;

        for (int i = 0; i < size; i++) {
            Pair<TreeNode, Integer> pair = queue.poll();
            TreeNode node = pair.getKey();
            int index = pair.getValue();
            rightmost = index;

            if (node.left != null) queue.offer(new Pair<>(node.left, 2 * index));
            if (node.right != null) queue.offer(new Pair<>(node.right, 2 * index + 1));
        }
        maxWidth = Math.max(maxWidth, rightmost - leftmost + 1);
    }
    return maxWidth;
}