class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 哈希表：记录「已经遍历过的数值 → 该数值所在下标」
        // 作用：O(1) 判断「补数」是否出现过，避免暴力双重循环
        Map<Integer, Integer> indexByValue = new HashMap<>();

        // 只遍历一遍数组，边查边存
        for (int i = 0; i < nums.length; i++) {
            // 当前数 nums[i] 想凑出 target，还差 need
            // 例如 target=9、nums[i]=2，则 need=7
            int need = target - nums[i];

            // 若 need 已在表中，说明前面某个位置 j 满足：
            // nums[j] + nums[i] == target，且 j != i（因为 i 还没入表）
            if (indexByValue.containsKey(need)) {
                // 返回 [补数下标, 当前下标]
                return new int[]{indexByValue.get(need), i};
            }

            // 没找到配对：把当前值写入表，留给后面的元素当「补数」用
            // 注意：必须先查再存，否则同一元素会被用两次（题目不允许）
            indexByValue.put(nums[i], i);
        }

        // 按题意一定有解；此处仅为防御性返回，实际不会走到
        int[] ans = new int[]{-1, -1};
        return ans;
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 哈希表：排序后的「签名」→ 属于该签名的所有原字符串
        // 例如 "eat" / "tea" / "ate" 排序后都是 "aet"，会进同一组
        Map<String, List<String>> groupsBySignature = new HashMap<>();

        for (String word : strs) {
            // 对当前串的字符排序，得到分组用的签名键
            char[] chars = word.toCharArray();
            Arrays.sort(chars);
            String signature = new String(chars);

            // 若该签名尚无分组则新建列表，再把原串加入对应组
            groupsBySignature
                .computeIfAbsent(signature, key -> new ArrayList<>())
                .add(word);
        }

        // 哈希表的 values 即为各组异位词；题目允许任意顺序
        List<List<String>> ans = new ArrayList<>(groupsBySignature.values());
        return ans;
    }
}

class Solution {
    public int longestConsecutive(int[] nums) {
        // 用 HashSet 去重，并支持 O(1) 判断某个数是否存在
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int ans = 0;

        // 遍历集合中的每个数，只从「连续序列的起点」开始向右扩展
        for (int num : numSet) {
            // 若存在 num-1，说明 num 不是起点，跳过，避免重复计算同一段
            if (numSet.contains(num - 1)) {
                continue;
            }

            // 从 num 开始向右探：num, num+1, num+2, ...
            int next = num + 1;
            while (numSet.contains(next)) {
                next++;
            }

            // next 停在「第一个不存在的数」，因此长度为 next - num
            ans = Math.max(ans, next - num);

            // 剪枝：已找到的长度不可能再被更长序列超过时提前结束
            // （最长连续长度至多等于去重后的元素个数）
            if (ans == numSet.size()) {
                break;
            }
        }

        return ans;
    }
}

class Solution {
    public void moveZeroes(int[] nums) {
        // left：下一个非零元素应该放入的下标（左侧 [0, left) 已是保持相对顺序的非零区）
        int left = 0;

        // right：扫描指针，负责发现每一个非零元素
        for (int right = 0; right < nums.length; right++) {
            if (nums[right] != 0) {
                // 把非零元素换到 left 位置；若 left == right，交换等价于原地不动
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;
                left++;
            }
        }
        // 循环结束时：[0, left) 为非零，[left, n) 全为 0
    }
}

class Solution {
    public int maxArea(int[] height) {
        int ans = 0;
        int left = 0;
        int right = height.length - 1;

        // 两端夹逼：宽度从最大开始往中间收缩
        while (left < right) {
            // 短板决定水位；面积 = 宽度 × 短板高度
            int boardHeight = Math.min(height[left], height[right]);
            ans = Math.max(ans, (right - left) * boardHeight);

            // 只移动较矮的一侧，才有机会提高短板、刷新最大面积
            // 两边等高时移动任意一侧均可（这里走 else，右指针左移）
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return ans;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            // 最小的三个数都 > 0，后面更大，不可能再有和为 0
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            // 相同的第一个数只枚举一次，避免重复三元组
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 当前数即使配上最大的两个数仍 < 0，换更大的 nums[i]
            if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < 0) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum < 0) {
                    left++;
                } else if (sum > 0) {
                    right--;
                } else {
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    // 跳过与刚加入解相同的左右值，保证不重复
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;
                    }
                }
            }
        }

        return ans;
    }
}

class Solution {
    public int trap(int[] height) {
        int left = 0;
        int right = height.length - 1;
        // 扫描过程中已见过的左侧 / 右侧最高柱
        int maxLeft = 0;
        int maxRight = 0;
        int ans = 0;

        while (left < right) {
            // 较矮一侧决定当前水位上界（另一侧必有不低于它的墙）
            if (height[left] <= height[right]) {
                maxLeft = Math.max(maxLeft, height[left]);
                // 当前位置能接到的雨水高度
                ans += maxLeft - height[left];
                left++;
            } else {
                maxRight = Math.max(maxRight, height[right]);
                ans += maxRight - height[right];
                right--;
            }
        }

        return ans;
    }
}

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int ans = 0;
        int left = 0;
        // 字符 → 最近一次出现的下标
        Map<Character, Integer> lastIndexByChar = new HashMap<>();

        for (int right = 0; right < s.length(); right++) {
            char current = s.charAt(right);
            // 若 current 曾出现在当前窗口内，左边界跳到「上次位置的下一位」
            // getOrDefault(..., -1)+1：从未出现过则仍从原 left 起
            left = Math.max(left, lastIndexByChar.getOrDefault(current, -1) + 1);
            ans = Math.max(ans, right - left + 1);
            lastIndexByChar.put(current, right);
        }

        return ans;
    }
}

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        int n = s.length();
        int m = p.length();
        if (n < m) {
            return ans;
        }

        int[] need = new int[26];
        int[] window = new int[26];
        // 先填满长度为 m 的首个窗口，并统计 p 的目标频次
        for (int i = 0; i < m; i++) {
            need[p.charAt(i) - 'a']++;
            window[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(need, window)) {
            ans.add(0);
        }

        // 窗口整体右移：右边进一个字符，左边出一个字符
        for (int right = m; right < n; right++) {
            window[s.charAt(right) - 'a']++;
            window[s.charAt(right - m) - 'a']--;
            if (Arrays.equals(need, window)) {
                // 当前窗口起点
                ans.add(right - m + 1);
            }
        }

        return ans;
    }
}

class Solution {
    public int subarraySum(int[] nums, int k) {
        // prefixSumCount：前缀和 → 该前缀和截止到当前位置之前出现了几次
        // 先放入 (0, 1)：表示「空前缀」出现过 1 次，对应从下标 0 开始的子数组
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        prefixSumCount.put(0, 1);

        int ans = 0;
        // prefixSum：nums[0..i] 的和（扫到 i 时的当前前缀和）
        int prefixSum = 0;

        for (int i = 0; i < nums.length; i++) {
            prefixSum += nums[i];

            // 若存在前缀和 = prefixSum - k，说明中间那段子数组之和恰为 k
            // 其出现次数都要累加进答案（多段不同起点可能对应同一差值）
            if (prefixSumCount.containsKey(prefixSum - k)) {
                ans += prefixSumCount.get(prefixSum - k);
            }

            // 再把当前前缀和登记进表，供后面的位置查询
            // 必须先查询再写入，避免把「当前这个前缀」误当成更早的起点
            prefixSumCount.put(prefixSum, prefixSumCount.getOrDefault(prefixSum, 0) + 1);
        }

        return ans;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        // ans[i]：以 i 为起点、长度为 k 的窗口的最大值
        int[] ans = new int[n - k + 1];

        // indexDeque：存下标，对应值在队内从大到小（单调递减）
        // 队头 indexDeque.peekFirst() 始终是「当前窗口内最大值」的下标
        Deque<Integer> indexDeque = new ArrayDeque<>();

        for (int right = 0; right < n; right++) {
            // 新元素更大，则它左边更小的候选再也不可能是最大值，从队尾清掉
            while (!indexDeque.isEmpty() && nums[indexDeque.peekLast()] <= nums[right]) {
                indexDeque.pollLast();
            }
            indexDeque.offerLast(right);

            // left：当前窗口的左边界（窗口为 [left, right]，长度 k）
            int left = right - k + 1;
            if (left < 0) {
                // 窗口尚未形成完整的 k 个元素
                continue;
            }

            // 队头下标已滑出窗口，过期，从队头丢弃
            while (indexDeque.peekFirst() < left) {
                indexDeque.pollFirst();
            }

            ans[left] = nums[indexDeque.peekFirst()];
        }

        return ans;
    }
}

class Solution {
    public String minWindow(String s, String t) {
        // need[c]：窗口相对目标还「欠」多少个字符 c
        //   >0 表示还缺；=0 表示刚好够；<0 表示窗口里该字符有多余
        int[] need = new int[128];
        // unsatisfiedKinds：t 中还有多少种字符尚未达到所需次数
        int unsatisfiedKinds = 0;

        for (char c : t.toCharArray()) {
            // 某种字符第一次被记入需求时，未满足种类数 +1
            if (need[c]++ == 0) {
                unsatisfiedKinds++;
            }
        }

        int left = 0;
        // bestLeft / bestRight：当前找到的最短合法窗口两端（闭区间）
        // 初始 bestRight-bestLeft 设得尽量大，表示尚未找到答案
        int bestLeft = -1;
        int bestRight = s.length();

        for (int right = 0; right < s.length(); right++) {
            char inChar = s.charAt(right);
            // 右端纳入 inChar：需求减 1；若从 1 减到 0，说明这种字符刚好达标
            if (--need[inChar] == 0) {
                unsatisfiedKinds--;
            }

            // 窗口已覆盖 t：尝试收缩左端，寻找更短覆盖
            while (unsatisfiedKinds == 0) {
                if (right - left < bestRight - bestLeft) {
                    bestLeft = left;
                    bestRight = right;
                }

                char outChar = s.charAt(left);
                // 左端移出 outChar：需求加 1；若从 0 加到 1，说明这种字符又开始缺
                if (need[outChar]++ == 0) {
                    unsatisfiedKinds++;
                }
                left++;
            }
        }

        String ans = (bestLeft == -1) ? "" : s.substring(bestLeft, bestRight + 1);
        return ans;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        // ans：全局最大子数组和（题目保证至少选一个元素）
        int ans = Integer.MIN_VALUE;
        // endingHere：以当前元素结尾的「最佳」连续子段和
        int endingHere = 0;

        for (int num : nums) {
            // 此前和为负：丢掉前面那段，从 num 重新开始
            // 此前和非负：把 num 接到后面，延续当前子段
            endingHere = endingHere < 0 ? num : endingHere + num;
            ans = Math.max(ans, endingHere);
        }

        return ans;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        // 按区间左端点升序，保证扫描时只可能与「上一段」合并
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // ans：已合并完成的区间列表（按左端点有序、互不重叠）
        List<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);

        for (int i = 1; i < intervals.length; i++) {
            // last：答案中当前最后一段，也是唯一可能与 intervals[i] 重叠的段
            int[] last = ans.get(ans.size() - 1);
            int[] cur = intervals[i];

            // 重叠或首尾相接：扩展 last 的右端
            if (last[1] >= cur[0]) {
                last[1] = Math.max(last[1], cur[1]);
            } else {
                // 与上一段脱节，开启新段
                ans.add(cur);
            }
        }

        return ans.toArray(new int[ans.size()][]);
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        // ans[j]：轮转后下标 j 应放的值
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            // 原下标 i 的元素右移 k 位后落到 (i + k) % n
            ans[(i + k) % n] = nums[i];
        }
        System.arraycopy(ans, 0, nums, 0, n);
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k %= n;
        // 一共有 gcd(k, n) 个独立环，每个环走一遍即可覆盖全部位置
        int cycles = gcd(k, n);
        for (int start = 0; start < cycles; start++) {
            int cur = start;
            int prev = nums[start]; // 手中正要放入下一位置的值
            do {
                int next = (cur + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                cur = next;
            } while (cur != start);
        }
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        // k 可能 ≥ n，取模后等价于实际需要右移的步数
        k %= n;

        // 三次反转：整体 → 前 k → 后 n-k
        // 例：[1,2,3,4,5,6,7], k=3
        // 整体反转 → [7,6,5,4,3,2,1]
        // 前 3 反转 → [5,6,7,4,3,2,1]
        // 后 4 反转 → [5,6,7,1,2,3,4]
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
    }

    // 原地反转闭区间 [left, right]
    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // left[i]：nums[0..i-1] 的乘积；right[i]：nums[i+1..n-1] 的乘积
        int[] left = new int[n];
        int[] right = new int[n];
        int[] ans = new int[n];

        left[0] = 1;
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }

        right[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++) {
            ans[i] = left[i] * right[i];
        }
        return ans;
    }
}

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // ans 先存左侧积，最后再原地乘上右侧积；它是输出，不算额外空间
        int[] ans = new int[n];
        ans[0] = 1; // 下标 0 左侧为空，前缀积约定为 1

        // 左 → 右：ans[i] = nums[0] * ... * nums[i-1]
        for (int i = 1; i < n; i++) {
            ans[i] = ans[i - 1] * nums[i - 1];
        }

        // suffixProduct：nums[i+1] * ... * nums[n-1]，滚动维护右侧积
        // 相当于把基础版的 right[] 压缩成一个变量
        int suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            ans[i] *= suffixProduct;
            suffixProduct *= nums[i];
        }

        return ans;
    }
}

class Solution {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 原地「哈希」：把值 x 放到下标 x-1（仅处理 1..n 范围内的数）
        for (int i = 0; i < n; i++) {
            // nums[i] 在 [1,n] 内，且目标坑位上还不是 nums[i] 本身（避免死循环）
            // 例：nums[i]=3 应换到下标 2；若 nums[2] 已是 3 则停止
            while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
                int targetIndex = nums[i] - 1; // 值 nums[i] 应去的下标
                int temp = nums[targetIndex];
                nums[targetIndex] = nums[i];
                nums[i] = temp;
            }
        }

        // 第一个不满足 nums[i] == i+1 的位置，缺失的就是 i+1
        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 1..n 全都在，答案只能是 n+1
        return n + 1;
    }
}

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // isCol0Zero：原矩阵第一列是否已经出现过 0
        // （第一列要单独记，因为 matrix[i][0] 还要兼作「第 i 行」的标记）
        boolean isCol0Zero = false;

        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                isCol0Zero = true;
            }
            // j 从 1 起：用第 0 列当行标记，故不在这里改写「第一列是否该清」以外的逻辑
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    // 行首、列首打标：表示整行 i / 整列 j 稍后要清零
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // 倒序填写，先用完第一行/第一列上的标记，再改它们自己
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 1; j--) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
            if (isCol0Zero) {
                matrix[i][0] = 0;
            }
        }
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ans = new ArrayList<>();
        // 当前仍未遍历的矩形边界（闭区间）
        int top = 0;
        int bottom = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;

        while (true) {
            // 1. 从左到右走完上边，然后上边界下移
            for (int j = left; j <= right; j++) {
                ans.add(matrix[top][j]);
            }
            if (++top > bottom) {
                break;
            }

            // 2. 从上到下走完右边，然后右边界左移
            for (int i = top; i <= bottom; i++) {
                ans.add(matrix[i][right]);
            }
            if (--right < left) {
                break;
            }

            // 3. 从右到左走完下边，然后下边界上移
            for (int j = right; j >= left; j--) {
                ans.add(matrix[bottom][j]);
            }
            if (--bottom < top) {
                break;
            }

            // 4. 从下到上走完左边，然后左边界右移
            for (int i = bottom; i >= top; i--) {
                ans.add(matrix[i][left]);
            }
            if (++left > right) {
                break;
            }
        }

        return ans;
    }
}

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // 1. 转置：沿主对角线交换，只扫上三角以免换两次又换回去
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 2. 每一行左右翻转：转置后再翻转 = 顺时针 90°
        for (int i = 0; i < n; i++) {
            int left = 0;
            int right = n - 1;
            while (left < right) {
                int temp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = temp;
                left++;
                right--;
            }
        }
    }
}

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 从右上角出发：左边更小，下边更大，便于二分支决策
        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            int cur = matrix[row][col];
            if (cur == target) {
                return true;
            }
            if (cur < target) {
                // 当前值偏小：本行左侧只会更小，整行可排除，下移一行
                row++;
            } else {
                // 当前值偏大：本列下方只会更大，整列可排除，左移一列
                col--;
            }
        }

        return false;
    }
}

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        // pA / pB：分别从 A、B 出发；走完本链后切换到另一条链的头
        ListNode pA = headA;
        ListNode pB = headB;

        // 相交时在交点相遇；不相交时同时变为 null，循环结束
        while (pA != pB) {
            // 走到末尾（null）就换到另一条链表头部，相当于补齐长度差
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        // ans：相交起始节点；不相交时为 null（此时 pA == pB == null）
        ListNode ans = pA;
        return ans;
    }
}

class Solution {
    // 「递」到末尾拿到新头；「归」时把经过的节点依次尾插到已反转链表末尾
    public ListNode reverseList(ListNode head) {
        // 空链表或只剩一个节点：已是反转结果（也是递的终点）
        if (head == null || head.next == null) {
            return head;
        }

        // ans：反转后的新头（原链表末节点），一路从递归深处传回来
        ListNode ans = reverseList(head.next);

        // tail：当前已反转段的末尾；递回来时 head.next 正好指向它
        ListNode tail = head.next;
        tail.next = head; // 把 head 尾插到已反转段后面
        head.next = null; // 必须断开，否则 head 与原后继互相指向成环

        return ans;
    }
}

class Solution {
    public ListNode reverseList(ListNode head) {
        // prev：已反转部分的头；初始为 null，表示新链表暂空
        ListNode prev = null;
        // curr：正在处理的节点
        ListNode curr = head;

        while (curr != null) {
            // next：先存后继，否则改 next 后会丢后面整段
            ListNode next = curr.next;
            curr.next = prev; // 当前节点头插到已反转链表
            prev = curr;      // prev 前进为新的「已反转头」
            curr = next;      // 继续处理原后继
        }

        // ans：反转后的头节点（原链表末节点）；curr 已走到 null
        ListNode ans = prev;
        return ans;
    }
}

class Solution {
    public boolean isPalindrome(ListNode head) {
        // mid：后半段起点（偶数时为右半第一个；奇数时为正中节点）
        ListNode mid = findMid(head);
        // head2：反转后半段后的新头，从尾向中逐个对齐
        ListNode head2 = reverse(mid);

        // ans：是否回文；默认 true，发现不等再改 false
        boolean ans = true;
        ListNode p1 = head;
        ListNode p2 = head2;
        // 只以后半长度为准：偶数比完右半即停；奇数多比一次中点与自身
        while (p2 != null) {
            if (p1.val != p2.val) {
                ans = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return ans;
    }

    // 快慢指针：fast 走两步、slow 走一步，fast 到末尾时 slow 在中点/右半起点
    private ListNode findMid(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // 迭代反转：把 curr 不断头插到 prev 前面，返回新头
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next; // 先存后继，避免断链后丢后面
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        // 空链或单节点且无自环：不可能形成环
        if (head == null || head.next == null) {
            return false;
        }

        // slow / fast：同起点；slow 走 1、fast 走 2
        ListNode slow = head;
        ListNode fast = head;
        // ans：是否存在环
        boolean ans = false;

        // fast 能走到 null 说明无环；能相遇说明有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ans = true;
                break;
            }
        }
        return ans;
    }
}

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

        // slow / fast：同起点判圈；相遇后用于找入口
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 相遇：把 slow 拉回头部，与 fast（仍在相遇点）同步各走 1 步
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                // ans：入环第一个节点（两指针再次相遇处）
                ListNode ans = slow;
                return ans;
            }
        }
        // 快指针走到末尾：无环
        return null;
    }
}

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        // dummy：虚头，避免单独处理「第一个节点」；最终 ans = dummy.next
        ListNode dummy = new ListNode();
        // curr：已合并段的尾节点，下一跳接到较小的那个
        ListNode curr = dummy;

        // 两边都还有节点：每次取较小者接到 curr 后面
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                curr.next = list2;
                list2 = list2.next;
            } else {
                // 相等时优先接 list1，顺序稳定即可
                curr.next = list1;
                list1 = list1.next;
            }
            curr = curr.next;
        }

        // 一条已空：把另一条剩余整段直接挂上（可能为 null）
        curr.next = (list1 == null) ? list2 : list1;

        // ans：合并后的真正头节点
        ListNode ans = dummy.next;
        return ans;
    }
}

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // dummy：虚头；curr 指向当前结果尾，便于尾插
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        // carry：来自上一位的进位，取值 0 或 1（两位最多 9+9+1）
        int carry = 0;

        // 只要还有数字或进位未消完就继续；短链缺位按 0
        while (carry != 0 || l1 != null || l2 != null) {
            int val1 = (l1 == null) ? 0 : l1.val;
            int val2 = (l2 == null) ? 0 : l2.val;
            int total = carry + val1 + val2;
            carry = total / 10;                 // 新进位
            curr.next = new ListNode(total % 10); // 本位写入结果
            curr = curr.next;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        // ans：和链表的真正头（个位）
        ListNode ans = dummy.next;
        return ans;
    }
}

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // dummy：虚头接在 head 前，删头时也能用同一套逻辑
        ListNode dummy = new ListNode(0, head);
        // slow / fast：同从 dummy 出发；最终 slow 停在待删结点前驱
        ListNode slow = dummy;
        ListNode fast = dummy;

        // fast 先拉开 n 步距离（此时 fast 与 slow 之间隔 n 个结点）
        while (n > 0) {
            fast = fast.next;
            n--;
        }

        // 同步前进，直到 fast 到达最后一个结点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 跳过倒数第 n 个结点
        slow.next = slow.next.next;

        // ans：可能已变的新头（原头被删时为原第二个结点）
        ListNode ans = dummy.next;
        return ans;
    }
}

class Solution {
    public ListNode swapPairs(ListNode head) {
        // dummy：虚头，统一处理「头两结点互换」后新头变化的情况
        ListNode dummy = new ListNode(0, head);
        // prev：当前待交换这一对的前驱
        ListNode prev = dummy;

        // 至少还有两个结点才交换；否则剩 0/1 个保持原样
        while (prev.next != null && prev.next.next != null) {
            // first / second：待交换的相邻两结点
            ListNode first = prev.next;
            ListNode second = first.next;

            // 重接：prev → second → first → (原 second 之后)
            prev.next = second;
            first.next = second.next;
            second.next = first;

            // 下一对的前驱变为交换后的 first（现位于对尾）
            prev = first;
        }

        // ans：交换后的头（可能仍是原 head，也可能是原第二个结点）
        ListNode ans = dummy.next;
        return ans;
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null) {
            return head;
        }

        // 先探：从 head 起是否还有至少 k 个结点
        ListNode curr = head;
        int count = 0;
        while (curr != null && count < k) {
            count++;
            curr = curr.next;
        }
        // 不足 k：剩余保持原序，直接返回本段原头
        if (count < k) {
            return head;
        }

        // 反转当前这 k 个：头插，结束后 prev 为本段新头，curr 为下一段起点
        ListNode prev = null;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // 原 head 已成段尾，接到「后面各段递归翻转」的结果
        head.next = reverseKGroup(curr, k);

        // ans：本段翻转后的新头
        ListNode ans = prev;
        return ans;
    }
}

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // dummy：虚头，方便连接每一组翻转后的新头
        ListNode dummy = new ListNode(0, head);
        // groupPrev：上一组的尾（也是下一组的前驱）
        ListNode groupPrev = dummy;

        while (true) {
            // kth：从 groupPrev 再走 k 步，得到本组最后一个结点
            ListNode kth = groupPrev;
            for (int i = 0; i < k; i++) {
                kth = kth.next;
                if (kth == null) {
                    // 不足 k 个：后面保持原序，直接结束
                    ListNode ans = dummy.next;
                    return ans;
                }
            }

            // groupNext：下一组起点；groupHead：本组原头（翻转后变组尾）
            ListNode groupNext = kth.next;
            ListNode groupHead = groupPrev.next;

            // 反转 [groupHead, kth]：断开与 groupNext 的连接后头插
            ListNode prev = groupNext;
            ListNode curr = groupHead;
            while (curr != groupNext) {
                ListNode next = curr.next;
                curr.next = prev;
                prev = curr;
                curr = next;
            }

            // 前驱接到本组新头 kth；原头变成组尾，作为下一组前驱
            groupPrev.next = kth;
            groupPrev = groupHead;
        }
    }
}

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }

        // 1. 交错插入副本：A → A' → B → B' → …
        Node curr = head;
        while (curr != null) {
            Node copy = new Node(curr.val);
            copy.next = curr.next;
            curr.next = copy;
            curr = copy.next; // 跳到下一个原节点
        }

        // 2. 给副本挂 random：副本紧跟原节点，故原.random 的副本 = 原.random.next
        curr = head;
        while (curr != null) {
            Node copy = curr.next;
            copy.random = (curr.random == null) ? null : curr.random.next;
            curr = copy.next;
        }

        // 3. 拆分：恢复原链表 next，同时串起副本链
        // ans：复制链表头（原 head 的紧后副本）
        Node ans = head.next;
        curr = head;
        while (curr != null) {
            Node copy = curr.next;
            // 原节点接回下一个原节点（跳过副本）
            curr.next = copy.next;
            // 副本接到下一个副本（若还有）
            copy.next = (curr.next == null) ? null : curr.next.next;
            curr = curr.next;
        }
        return ans;
    }
}

class Solution {
    public ListNode sortList(ListNode head) {
        int length = getListLength(head);
        // dummy：整表前驱，方便每轮把合并结果重新挂回
        ListNode dummy = new ListNode(0, head);

        // step：本轮参与合并的有序段长度；每轮结束后有序段变长为 2*step
        for (int step = 1; step < length; step *= 2) {
            // newListTail：本轮已合并部分的尾，下一段合并结果接在其后
            ListNode newListTail = dummy;
            // cur：尚未处理的剩余链表起点
            ListNode cur = dummy.next;

            while (cur != null) {
                // head1 / head2：切出两段长至多为 step 的链表
                ListNode head1 = cur;
                ListNode head2 = splitList(head1, step);
                cur = splitList(head2, step); // 下一段起点（可能为 null）

                // merged[0]/合并后头；merged[1]=合并后尾
                ListNode[] merged = mergeTwoLists(head1, head2);
                newListTail.next = merged[0];
                newListTail = merged[1];
            }
        }

        // ans：排序后的链表头
        ListNode ans = dummy.next;
        return ans;
    }

    private int getListLength(ListNode head) {
        int length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }
        return length;
    }

    // 合并两条有序链表，返回 {头, 尾}，便于外层 O(1) 接上一段
    private ListNode[] mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        cur.next = (list1 != null) ? list1 : list2;
        while (cur.next != null) {
            cur = cur.next; // 走到合并结果真正的尾
        }
        return new ListNode[]{dummy.next, cur};
    }

    // 从 head 起切出前 size 个结点并断开；返回剩余段头。长度 ≤ size 则不切，返回 null
    private ListNode splitList(ListNode head, int size) {
        if (head == null) {
            return null;
        }
        ListNode cur = head;
        for (int i = 0; i < size - 1 && cur != null; i++) {
            cur = cur.next;
        }
        if (cur == null || cur.next == null) {
            return null;
        }
        ListNode nextHead = cur.next;
        cur.next = null; // 断开，使前 size 个成为独立链表
        return nextHead;
    }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 空数组 / null：没有可合并的链
        if (lists == null || lists.length == 0) {
            return null;
        }

        // dummy / curr：结果链虚头与当前尾
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        // pq：小根堆，存各链表「当前未合并的头」；比较结点 val
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode list : lists) {
            if (list != null) {
                pq.offer(list);
            }
        }

        while (!pq.isEmpty()) {
            // minNode：当前所有候选头中值最小者
            ListNode minNode = pq.poll();
            curr.next = minNode;
            curr = curr.next;
            // 该链还有后继则作为新候选入堆
            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }

        // ans：合并后的升序链表头
        ListNode ans = dummy.next;
        return ans;
    }
}

class LRUCache {
    // 双向链表结点：同时存 key，便于从尾删除时同步 map.remove
    class DLinkNode {
        int key;
        int value;
        DLinkNode prev;
        DLinkNode next;

        DLinkNode() {
        }

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

    private final DLinkNode head; // 假头：head.next 为最近使用
    private final DLinkNode tail; // 假尾：tail.prev 为最久未用
    private int size;
    private final int capacity;
    // map：key → 对应链表结点，实现 O(1) 查找
    private final Map<Integer, DLinkNode> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.map = new HashMap<>();
        head = new DLinkNode();
        tail = new DLinkNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkNode node = map.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node); // 访问即视为最近使用
        return node.value;
    }

    public void put(int key, int value) {
        DLinkNode node = map.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }

        // 新 key：头插；超容量则逐出最久未用（假尾前一个）
        DLinkNode newNode = new DLinkNode(key, value);
        addToHead(newNode);
        map.put(key, newNode);
        size++;
        if (size > capacity) {
            DLinkNode evicted = removeTail();
            map.remove(evicted.key);
            size--;
        }
    }

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

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

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

    // 删除并返回最久未使用结点（tail 前驱）
    private DLinkNode removeTail() {
        DLinkNode node = tail.prev;
        removeNode(node);
        return node;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        // ans：中序访问序列
        List<Integer> ans = new ArrayList<>();

        while (root != null) {
            if (root.left != null) {
                // prev：左子树中「中序意义下」的前驱，即左子树最右结点
                TreeNode prev = root.left;
                while (prev.right != null && prev.right != root) {
                    prev = prev.right;
                }

                if (prev.right == null) {
                    // 第一次到达：建立线索 prev.right → root，再深入左子树
                    prev.right = root;
                    root = root.left;
                    continue;
                }
                // 第二次到达：左子树已遍历完，拆除线索
                prev.right = null;
            }

            // 无左子树，或左子树刚遍历完：访问当前根，再走右
            ans.add(root.val);
            root = root.right;
        }
        return ans;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        // stack：待处理的祖先结点；沿左链压栈，弹出时访问再转右
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left; // 一路向左
            }
            cur = stack.pop();  // 左空：访问根
            ans.add(cur.val);
            cur = cur.right;    // 再处理右子树
        }
        return ans;
    }
}

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // left / right：左右子树的最大深度
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        // ans：当前树的最大深度 = 较高子树深度 + 本层 1
        int ans = Math.max(left, right) + 1;
        return ans;
    }
}

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        // left / right：翻转后的左右子树根
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        // 交换左右孩子，完成当前结点的镜像
        root.left = right;
        root.right = left;

        // ans：翻转后仍以原 root 为根
        TreeNode ans = root;
        return ans;
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        // ans：左右子树是否互为镜像
        boolean ans = check(root.left, root.right);
        return ans;
    }

    // 判断 node1、node2 为根的两棵树是否镜像对称
    private boolean check(TreeNode node1, TreeNode node2) {
        if (node1 == null || node2 == null) {
            // 只有两侧都空才对称；一空一非空则否
            return node1 == null && node2 == null;
        }
        if (node1.val != node2.val) {
            return false;
        }
        // 外侧对外侧、内侧对内侧
        return check(node1.left, node2.right) && check(node1.right, node2.left);
    }
}

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        // queue：成对存放待比较的镜像位置结点
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root.left != null) {
            queue.offer(root.left);
        }
        if (root.right != null) {
            queue.offer(root.right);
        }
        // 一侧有孩子、另一侧没有：队列长度必为奇数，直接不对称
        if (queue.size() == 1) {
            return false;
        }

        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if (node1.val != node2.val) {
                return false;
            }
            // 外侧：node1.left ↔ node2.right
            if (node1.left != null || node2.right != null) {
                if (node1.left == null || node2.right == null) {
                    return false;
                }
                queue.offer(node1.left);
                queue.offer(node2.right);
            }
            // 内侧：node1.right ↔ node2.left
            if (node1.right != null || node2.left != null) {
                if (node1.right == null || node2.left == null) {
                    return false;
                }
                queue.offer(node1.right);
                queue.offer(node2.left);
            }
        }

        boolean ans = true;
        return ans;
    }
}

class Solution {
    // ans：全局最大直径（边数）
    private int ans = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return ans;
    }

    // 返回以 root 为根的子树高度（结点数）；空树为 0
    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // left / right：左右子树高度
        int left = depth(root.left);
        int right = depth(root.right);
        // 经过当前结点的路径边数 = 左高 + 右高
        ans = Math.max(ans, left + right);
        return Math.max(left, right) + 1;
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        // ans：按层存放的遍历结果
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        // curr：当前层待处理结点
        Queue<TreeNode> curr = new ArrayDeque<>();
        curr.offer(root);

        while (!curr.isEmpty()) {
            // level：本层从左到右的结点值
            List<Integer> level = new ArrayList<>();
            // next：下一层结点（本层所有孩子）
            Queue<TreeNode> next = new ArrayDeque<>();

            while (!curr.isEmpty()) {
                TreeNode node = curr.poll();
                level.add(node.val);
                if (node.left != null) {
                    next.offer(node.left);
                }
                if (node.right != null) {
                    next.offer(node.right);
                }
            }

            ans.add(level);
            curr = next; // 进入下一层
        }
        return ans;
    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // ans：由整个数组区间建成的平衡 BST 根
        TreeNode ans = build(nums, 0, nums.length - 1);
        return ans;
    }

    // 用 nums[start..end] 建平衡 BST，返回子树根
    private TreeNode build(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        // mid：取中点作根，保证左右规模尽量均衡
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, start, mid - 1);
        root.right = build(nums, mid + 1, end);
        return root;
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        // ans：整棵树是否为合法 BST；初始开区间为全体 long
        boolean ans = validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
        return ans;
    }

    // 判断以 root 为根的子树是否合法，且所有结点值均满足 min < val < max
    private boolean validate(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        // 当前值必须严格落在 (min, max) 内
        if (root.val <= min || root.val >= max) {
            return false;
        }
        // 左子树：上界收紧为 root.val；右子树：下界收紧为 root.val
        return validate(root.left, min, root.val)
                && validate(root.right, root.val, max);
    }
}

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        // Morris 中序：按升序逐个访问，数到第 k 个
        while (root != null) {
            if (root.left != null) {
                // prev：左子树最右结点（中序前驱）
                TreeNode prev = root.left;
                while (prev.right != null && prev.right != root) {
                    prev = prev.right;
                }

                if (prev.right == null) {
                    // 第一次：建线索后走左
                    prev.right = root;
                    root = root.left;
                    continue;
                }
                // 第二次：左子树已遍历完，拆线索
                prev.right = null;
            }

            // 访问当前结点（中序位置）
            k--;
            if (k == 0) {
                // ans：第 k 小的值
                int ans = root.val;
                return ans;
            }
            root = root.right;
        }
        return -1; // 题目保证 1 <= k <= n，正常不会走到
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        // ans：自上而下每一层最右侧结点的值
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

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

        while (!queue.isEmpty()) {
            // size：本层结点数；用于划层
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
                // 本层最后一个出队的结点 = 右视图上的点
                if (size == 0) {
                    ans.add(node.val);
                }
            }
        }
        return ans;
    }
}

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        if (root.left != null) {
            // prev：左子树最右结点（先序下左子树的最后一个）
            TreeNode prev = root.left;
            while (prev.right != null) {
                prev = prev.right;
            }
            // 原右子树接到左子树末尾，保证先序「左完接右」
            prev.right = root.right;
            // 左子树整体挪到 right，left 清空
            root.right = root.left;
            root.left = null;
        }
        // 继续展开下一段（现已是原左或原右）
        flatten(root.right);
    }
}

class Solution {
    public void flatten(TreeNode root) {
        // 与解法一相同，沿 right 迭代推进，无递归栈
        while (root != null) {
            if (root.left != null) {
                TreeNode prev = root.left;
                while (prev.right != null) {
                    prev = prev.right;
                }
                prev.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }
}

class Solution {
    // indexMap：中序遍历中「值 → 下标」，避免每次线性找根
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        indexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            indexMap.put(inorder[i], i);
        }
        // ans：整棵树的根
        TreeNode ans = build(preorder, 0, preorder.length - 1, 0, inorder.length - 1);
        return ans;
    }

    // 用 preorder[preL..preR]、inorder[inL..inR] 对应区间建子树
    private TreeNode build(int[] preorder, int preL, int preR, int inL, int inR) {
        if (preL > preR) {
            return null;
        }
        // 先序区间第一个即当前根
        int rootVal = preorder[preL];
        TreeNode root = new TreeNode(rootVal);
        // rootIndex：根在中序中的位置；左侧长度为左子树结点个数
        int rootIndex = indexMap.get(rootVal);
        int leftLen = rootIndex - inL;

        // 先序：根后紧跟 leftLen 个是左子树，其余是右子树
        root.left = build(preorder, preL + 1, preL + leftLen, inL, rootIndex - 1);
        root.right = build(preorder, preL + leftLen + 1, preR, rootIndex + 1, inR);
        return root;
    }
}

class Solution {
    // ans：满足条件的路径条数
    private int ans = 0;
    // prefixSum：当前路径上「前缀和 → 出现次数」
    private Map<Long, Integer> prefixSum;

    public int pathSum(TreeNode root, int targetSum) {
        prefixSum = new HashMap<>();
        prefixSum.put(0L, 1); // 空前缀：路径从根开始时也能命中
        dfs(root, 0L, targetSum);
        return ans;
    }

    private void dfs(TreeNode root, long curr, int targetSum) {
        if (root == null) {
            return;
        }
        // currSum：根 → 当前结点的路径和
        long currSum = curr + root.val;
        // 若存在前缀 currSum - targetSum，则中间一段和为 targetSum
        ans += prefixSum.getOrDefault(currSum - targetSum, 0);

        prefixSum.put(currSum, prefixSum.getOrDefault(currSum, 0) + 1);
        dfs(root.left, currSum, targetSum);
        dfs(root.right, currSum, targetSum);
        // 回溯：离开当前结点，恢复 map，避免影响兄弟分支
        prefixSum.put(currSum, prefixSum.get(currSum) - 1);
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 命中目标或走到空：直接返回（题目保证 p、q 都在树中）
        if (root == null || root == p || root == q) {
            return root;
        }

        // left / right：左右子树中「找到的 p 或 q 或已求得的 LCA」
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);

        // 两侧都找到：p、q 分居左右，root 为最近公共祖先
        if (left != null && right != null) {
            return root;
        }
        // 只在一侧：LCA 在该侧（或该侧返回的就是 p/q 本身）
        TreeNode ans = (left != null) ? left : right;
        return ans;
    }
}

class Solution {
    // ans：全局最大路径和（至少含一个结点，初值取极小）
    private int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return ans;
    }

    // 返回：从 node 出发向下单边延伸时，能贡献给父结点的最大和（可为 0 表示不选）
    private int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // leftGain / rightGain：左右子树的单边最大贡献；负贡献直接丢弃
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 以当前结点为「最高点」同时连接左右时的路径和
        int pathThrough = node.val + leftGain + rightGain;
        ans = Math.max(ans, pathThrough);

        // 父结点只能接一侧，取较大边
        return node.val + Math.max(leftGain, rightGain);
    }
}