class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();

        while (root != null) {
            if (root.left != null) {
                // 找 root 的前驱 pre：左子树里「最右」的结点
                // 从 root.left 一直向右，直到尽头，或遇到已指向 root 的线索
                TreeNode pre = root.left;
                while (pre.right != null && pre.right != root) {
                    pre = pre.right;
                }

                // 左子树尚未访问：先记录根（前序），再建立线索并走左
                if (pre.right == null) {
                    ans.add(root.val); // 前序：第一次到达就访问根（与中序的差别）
                    pre.right = root;  // 建立线索（回到 root 的路），相当于把 pre.right 当栈
                    root = root.left;
                    continue;
                }

                // 左子树已访问完：拆掉线索，恢复原样
                pre.right = null; // 若调用后不再使用该树，这行可省略
                root = root.right;
            } else {
                // 无左子树：访问根，再走右
                ans.add(root.val);
                root = root.right;
            }
        }

        return ans;
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ans.add(node.val); // 先访问根
            // 先压右再压左，保证弹出时左先于右
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return ans;
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        preOrder(root, ans);
        return ans;
    }

    private void preOrder(TreeNode node, List<Integer> ans) {
        if (node == null) {
            return;
        }
        ans.add(node.val);       // 根
        preOrder(node.left, ans);  // 左
        preOrder(node.right, ans); // 右
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();

        // 镜像前序：根 → 右 → 左，最后整体反转即后序
        while (root != null) {
            if (root.right != null) {
                // 找「后继」：右子树里最左结点，用来挂回到 root 的线索
                TreeNode pre = root.right;
                while (pre.left != null && pre.left != root) {
                    pre = pre.left;
                }

                // 右子树尚未访问：先记录根，再建线索并走右
                if (pre.left == null) {
                    ans.add(root.val);
                    pre.left = root; // 线索：走完右子树后回到 root
                    root = root.right;
                    continue;
                }

                // 右子树已访问完：拆线索，走左
                pre.left = null;
                root = root.left;
            } else {
                // 无右子树：访问根，再走左
                ans.add(root.val);
                root = root.left;
            }
        }

        Collections.reverse(ans); // 根右左 → 左右根
        return ans;
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        // 先得到「根 → 右 → 左」，再反转
        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            ans.add(node.val);
            // 先压左再压右，弹出时右先于左
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(ans);
        return ans;
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        postOrder(root, ans);
        return ans;
    }

    private void postOrder(TreeNode node, List<Integer> ans) {
        if (node == null) {
            return;
        }
        postOrder(node.left, ans);  // 左
        postOrder(node.right, ans); // 右
        ans.add(node.val);          // 根
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();

        while (root != null) {
            if (root.left != null) {
                // 找 root 的前驱 pre：在中序遍历中，root 的上一个节点
                // 从 root.left 开始，一直向右走，直到走到尽头，或者遇到指向 root 的线索
                TreeNode pre = root.left;
                while (pre.right != null && pre.right != root) {
                    pre = pre.right;
                }

                // root 的左子树尚未访问
                if (pre.right == null) {
                    pre.right = root; // 建立线索（回到 root 的路），相当于把 pre.right 当作栈
                    root = root.left; // 访问左子树
                    continue;
                }

                // root 的左子树访问完毕，去掉线索，恢复原样
                pre.right = null; // 若调用后不再使用该树，这行可省略
            }

            // 无左子树，或左子树已访问完：记录当前节点，再走右
            ans.add(root.val);
            root = root.right;
        }

        return ans;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        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 List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inOrder(root, ans);
        return ans;
    }

    private void inOrder(TreeNode node, List<Integer> ans) {
        if (node == null) {
            return;
        }
        inOrder(node.left, ans);  // 左
        ans.add(node.val);        // 根
        inOrder(node.right, ans); // 右
    }
}

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size(); // 本层结点个数
            List<Integer> level = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                level.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size(); // 当前层节点数
            List<Integer> level = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                level.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ans.add(level); // 先自顶向下收集
        }

        Collections.reverse(ans); // 再整体反转 → 自底向上
        return ans;
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root, 0, ans);
        return ans;
    }

    // depth：当前深度；ans.size() 表示已记录到的最大深度+1
    private void dfs(TreeNode node, int depth, List<Integer> ans) {
        if (node == null) {
            return;
        }
        if (depth == ans.size()) {
            ans.add(node.val); // 该深度首次到达 = 最右侧
        }
        dfs(node.right, depth + 1, ans); // 先右
        dfs(node.left, depth + 1, ans);
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (i == size - 1) {
                    ans.add(node.val); // 本层最后一个 = 右视图
                }
            }
        }
        return ans;
    }
}

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Long> levelSum = new ArrayList<>();
        List<Integer> levelCnt = new ArrayList<>();
        dfs(root, 0, levelSum, levelCnt);

        List<Double> ans = new ArrayList<>(levelCnt.size());
        for (int i = 0; i < levelCnt.size(); i++) {
            ans.add(levelSum.get(i) * 1.0 / levelCnt.get(i));
        }
        return ans;
    }

    private void dfs(TreeNode node, int depth, List<Long> levelSum, List<Integer> levelCnt) {
        if (node == null) {
            return;
        }
        if (depth == levelCnt.size()) {
            // 第一次到达该深度：新建一层
            levelCnt.add(1);
            levelSum.add((long) node.val);
        } else {
            levelCnt.set(depth, levelCnt.get(depth) + 1);
            levelSum.set(depth, levelSum.get(depth) + node.val);
        }
        dfs(node.left, depth + 1, levelSum, levelCnt);
        dfs(node.right, depth + 1, levelSum, levelCnt);
    }
}

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>(size);
            for (int i = 0; i < size; i++) {
                Node cur = queue.poll();
                level.add(cur.val);
                // N 叉：所有孩子依次入队
                for (Node child : cur.children) {
                    queue.offer(child);
                }
            }
            ans.add(level);
        }
        return ans;
    }
}

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE; // 本层最大值
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                max = Math.max(max, cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ans.add(max);
        }
        return ans;
    }
}

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        // leftmost：当前层最左结点；完美二叉树有左孩子则必有下一层
        Node leftmost = root;
        while (leftmost.left != null) {
            Node head = leftmost;
            while (head != null) {
                // 同一父结点下的左右孩子
                head.left.next = head.right;
                // 跨父结点：右孩子接到隔壁的左孩子
                if (head.next != null) {
                    head.right.next = head.next.left;
                }
                head = head.next;
            }
            leftmost = leftmost.left; // 下到下一层最左
        }
        return root;
    }
}

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

class Solution {
    public Node connect(Node root) {
        Node curr = root; // 当前层最左结点；沿 next 当作链表遍历本层
        while (curr != null) {
            Node dummy = new Node(0); // 下一层虚头，方便统一接孩子
            Node tail = dummy;        // 下一层已接好的链尾

            // 本层已由 next 串好，从左扫到右，按出现顺序挂上下一层的孩子
            for (Node node = curr; node != null; node = node.next) {
                if (node.left != null) {
                    tail.next = node.left;
                    tail = tail.next;
                }
                if (node.right != null) {
                    tail.next = node.right;
                    tail = tail.next;
                }
            }
            curr = dummy.next; // 进入下一层（可能为 null，循环结束）
        }
        return root;
    }
}

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

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 叶子：左右都空
        if (root.left == null && root.right == null) {
            return 1;
        }
        // 空孩子不参与 min（避免被当成深度 0）
        int left = root.left != null ? minDepth(root.left) : Integer.MAX_VALUE;
        int right = root.right != null ? minDepth(root.right) : Integer.MAX_VALUE;
        return Math.min(left, right) + 1;
    }
}

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

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

    // 判断两棵树是否互为镜像
    private boolean check(TreeNode a, TreeNode b) {
        if (a == null || b == null) {
            return a == null && b == null; // 必须同时为空
        }
        if (a.val != b.val) {
            return false;
        }
        return check(a.left, b.right) && check(a.right, b.left);
    }
}

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // h：根到最左叶的边数；h==0 表示只有根
        int h = 0;
        TreeNode cur = root;
        while (cur.left != null) {
            h++;
            cur = cur.left;
        }
        if (h == 0) {
            return 1;
        }

        // 二分最后一层：找最右仍存在的下标 low（0-based）
        int low = 0;
        int high = (1 << h) - 1;
        while (low < high) {
            int mid = low + ((high - low + 1) >> 1); // 偏右中点，避免死循环
            if (exists(root, h, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        // 上层满树 2^h-1 + 最后一层 low+1 个结点
        int ans = (1 << h) - 1 + low + 1;
        return ans;
    }

    // 按完全二叉树堆下标：从高到低看 idx 各位，0 走左、1 走右
    private boolean exists(TreeNode root, int h, int idx) {
        int mask = 1 << (h - 1);
        TreeNode node = root;
        while (mask > 0 && node != null) {
            node = (idx & mask) == 0 ? node.left : node.right;
            mask >>= 1;
        }
        return node != null;
    }
}

class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    // 返回子树高度；若不平衡返回 -1
    private int height(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = height(node.left);
        if (left == -1) {
            return -1; // 左子树已不平衡，剪枝
        }
        int right = height(node.right);
        if (right == -1) {
            return -1;
        }
        if (Math.abs(left - right) > 1) {
            return -1;
        }
        return Math.max(left, right) + 1;
    }
}

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> ans = new ArrayList<>();
        if (root == null) {
            return ans;
        }
        StringBuilder path = new StringBuilder();
        dfs(root, path, ans);
        return ans;
    }

    private void dfs(TreeNode node, StringBuilder path, List<String> ans) {
        int len = path.length(); // 记录回溯点
        path.append(node.val);

        // 叶子：形成一条完整路径
        if (node.left == null && node.right == null) {
            ans.add(path.toString());
        } else {
            path.append("->");
            if (node.left != null) {
                dfs(node.left, path, ans);
            }
            if (node.right != null) {
                dfs(node.right, path, ans);
            }
        }

        path.setLength(len); // 回溯，恢复进入本结点前的状态
    }
}

class Solution {
    private int ans;

    public int sumOfLeftLeaves(TreeNode root) {
        ans = 0;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        // 左孩子存在且为叶子 → 计入答案
        if (node.left != null) {
            if (node.left.left == null && node.left.right == null) {
                ans += node.left.val;
            } else {
                dfs(node.left);
            }
        }
        dfs(node.right);
    }
}

class Solution {
    private int ans;
    private int maxDepth = -1;

    public int findBottomLeftValue(TreeNode root) {
        dfs(root, 0);
        return ans;
    }

    private void dfs(TreeNode node, int depth) {
        if (node == null) {
            return;
        }
        // 先左后右：同一深度第一次到达的是最左
        if (depth > maxDepth) {
            maxDepth = depth;
            ans = node.val;
        }
        dfs(node.left, depth + 1);
        dfs(node.right, depth + 1);
    }
}

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int ans = root.val;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                if (i == 0) {
                    ans = cur.val; // 本层最左；最后一层留下的即答案
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return ans;
    }
}

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        boolean ans = dfs(root, targetSum);
        return ans;
    }

    // remain：从当前结点出发还需要凑的路径和
    private boolean dfs(TreeNode node, int remain) {
        if (node == null) {
            return false; // 空不是合法路径；也覆盖整树为空
        }
        if (node.left == null && node.right == null) {
            return remain == node.val; // 必须到叶子才判定
        }
        return dfs(node.left, remain - node.val)
                || dfs(node.right, remain - node.val);
    }
}

class Solution {
    private Map<Integer, Integer> inIndex; // 中序值 -> 下标

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

    // pre[preL..preR]、in[inL..inR] 对应同一棵子树
    private TreeNode build(int[] preorder, int preL, int preR, int inL, int inR) {
        if (preL > preR) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preL]);
        int index = inIndex.get(root.val); // 根在中序中的位置
        int leftCnt = index - inL;         // 左子树结点个数

        root.left = build(preorder, preL + 1, preL + leftCnt, inL, index - 1);
        root.right = build(preorder, preL + leftCnt + 1, preR, index + 1, inR);
        return root;
    }
}

class Solution {
    private Map<Integer, Integer> inIndex; // 中序值 -> 下标

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

    // in[inL..inR]、post[postL..postR] 对应同一棵子树
    private TreeNode build(int[] inorder, int inL, int inR, int[] postorder, int postL, int postR) {
        if (postL > postR) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postR]); // 后序末尾是根
        int index = inIndex.get(root.val);
        int leftCnt = index - inL; // 左子树结点个数

        root.left = build(inorder, inL, index - 1, postorder, postL, postL + leftCnt - 1);
        root.right = build(inorder, index + 1, inR, postorder, postL + leftCnt, postR - 1);
        return root;
    }
}

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        Deque<TreeNode> stack = new ArrayDeque<>(); // 栈顶到栈底：值递减
        for (int val : nums) {
            TreeNode cur = new TreeNode(val);
            // 弹出所有比 cur 小的结点；最后弹出的是 cur 左子树的根
            while (!stack.isEmpty() && stack.peek().val < val) {
                cur.left = stack.pop();
            }
            // 若仍有更大的前驱，cur 成为其右孩子
            if (!stack.isEmpty()) {
                stack.peek().right = cur;
            }
            stack.push(cur);
        }
        // 不断弹出后剩下的栈底是全局最大值，即 ans
        TreeNode ans = null;
        while (!stack.isEmpty()) {
            ans = stack.pop();
        }
        return ans;
    }
}

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2; // 左树空，整段右树可直接复用
        }
        if (root2 == null) {
            return root1; // 右树空，整段左树可直接复用
        }
        // 两侧都非空：新建结点，值相加，再递归合并左右孩子
        TreeNode ans = new TreeNode(root1.val + root2.val);
        ans.left = mergeTrees(root1.left, root2.left);
        ans.right = mergeTrees(root1.right, root2.right);
        return ans;
    }
}

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        TreeNode ans = root;
        while (ans != null && ans.val != val) {
            // 小于当前值 → 答案只可能在左子树；否则在右子树
            ans = val < ans.val ? ans.left : ans.right;
        }
        return ans; // 命中返回该结点子树根；走到 null 则不存在
    }
}

class Solution {
    public boolean isValidBST(TreeNode root) {
        // 初始开区间 (-∞, +∞)；用 long 包住 int 全范围
        return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 判断以 root 为根的子树是否所有结点都满足 min < val < max
    private boolean dfs(TreeNode root, long min, long max) {
        if (root == null) {
            return true;
        }
        if (root.val <= min || root.val >= max) {
            return false; // 不在开区间内（BST 要求严格小于/大于）
        }
        // 左：(min, root.val)；右：(root.val, max)
        return dfs(root.left, min, root.val) && dfs(root.right, root.val, max);
    }
}

class Solution {
    public int getMinimumDifference(TreeNode root) {
        int ans = Integer.MAX_VALUE;
        int prevVal = 0; // 中序上一个已访问结点的值
        boolean isFirst = true; // 尚无前驱时不比较

        while (root != null) {
            if (root.left != null) {
                // 找中序前驱：左子树一路向右
                TreeNode predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                if (predecessor.right == null) {
                    predecessor.right = root; // 建线索，先走左
                    root = root.left;
                    continue;
                }
                predecessor.right = null; // 第二次到达：拆线索
            }
            // 中序访问当前结点
            if (!isFirst) {
                ans = Math.min(ans, root.val - prevVal); // 有序，差非负
            }
            prevVal = root.val;
            isFirst = false;
            root = root.right;
        }
        return ans;
    }
}

class Solution {
    public int[] findMode(TreeNode root) {
        int maxCnt = 0;
        int curCnt = 0;
        Integer prev = null;

        // 第一遍 Morris：求最大频次
        TreeNode curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    pred.right = curr;
                    curr = curr.left;
                    continue;
                }
                pred.right = null;
            }
            // 中序访问
            if (prev != null && curr.val == prev) {
                curCnt++;
            } else {
                curCnt = 1; // 换值时从 1 开始，不要置 0
            }
            maxCnt = Math.max(maxCnt, curCnt);
            prev = curr.val;
            curr = curr.right;
        }

        // 第二遍：统计众数个数，再开定长数组
        int modeNum = 0;
        curCnt = 0;
        prev = null;
        curr = root;
        while (curr != null) {
            if (curr.left != null) {
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    pred.right = curr;
                    curr = curr.left;
                    continue;
                }
                pred.right = null;
            }
            if (prev != null && curr.val == prev) {
                curCnt++;
            } else {
                curCnt = 1;
            }
            if (curCnt == maxCnt) {
                modeNum++; // 每个众数值在「达到 maxCnt 的那一次」计一次
            }
            prev = curr.val;
            curr = curr.right;
        }

        int[] ans = new int[modeNum];
        int idx = 0;
        curCnt = 0;
        prev = null;
        curr = root;
        // 第三遍：写入 ans
        while (curr != null) {
            if (curr.left != null) {
                TreeNode pred = curr.left;
                while (pred.right != null && pred.right != curr) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    pred.right = curr;
                    curr = curr.left;
                    continue;
                }
                pred.right = null;
            }
            if (prev != null && curr.val == prev) {
                curCnt++;
            } else {
                curCnt = 1;
            }
            if (curCnt == maxCnt) {
                ans[idx++] = curr.val;
            }
            prev = curr.val;
            curr = curr.right;
        }
        return ans;
    }
}

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 空，或命中 p/q：题目保证二者都在树中，可直接返回
        if (root == null || root == p || root == q) {
            return root;
        }

        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 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode ans = root;
        while (ans != null) {
            if (ans.val < p.val && ans.val < q.val) {
                ans = ans.right; // p、q 都在右子树
            } else if (ans.val > p.val && ans.val > q.val) {
                ans = ans.left; // p、q 都在左子树
            } else {
                // 分居两侧，或 ans 等于 p/q 之一
                return ans;
            }
        }
        return null; // 题目保证存在，实际不会走到
    }
}

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            return node; // 空树：新结点即根
        }
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) {
                    cur.left = node; // 找到左空位插入
                    break;
                }
                cur = cur.left;
            } else { // 题目保证 val 不与已有值重复
                if (cur.right == null) {
                    cur.right = node;
                    break;
                }
                cur = cur.right;
            }
        }
        return root; // 原根不变（非空时）
    }
}

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        TreeNode dummy = new TreeNode(0); // 哨兵：dummy.right 始终指向当前树根
        dummy.right = root;
        TreeNode parent = dummy;
        TreeNode cur = root;

        // 定位待删结点，并记录其父结点
        while (cur != null && cur.val != key) {
            parent = cur;
            cur = key < cur.val ? cur.left : cur.right;
        }
        if (cur == null) {
            return dummy.right; // 未找到，原树不变
        }

        if (cur.left == null || cur.right == null) {
            // 0 或 1 个孩子：用仅有的孩子（或 null）顶替 cur
            TreeNode child = cur.left != null ? cur.left : cur.right;
            if (parent.left == cur) {
                parent.left = child;
            } else {
                parent.right = child;
            }
        } else {
            // 双孩子：后继 = 右子树最左；左子树挂到后继左侧，右子树顶替 cur
            TreeNode succ = cur.right;
            while (succ.left != null) {
                succ = succ.left;
            }
            succ.left = cur.left;
            if (parent.left == cur) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        }

        TreeNode ans = dummy.right;
        return ans;
    }
}

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return null;
        }
        if (root.val < low) {
            // 当前及左子树都 < low，答案只可能在右子树
            return trimBST(root.right, low, high);
        }
        if (root.val > high) {
            // 当前及右子树都 > high，答案只可能在左子树
            return trimBST(root.left, low, high);
        }
        // 当前保留，递归修剪左右
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        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;
        }
        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 TreeNode convertBST(TreeNode root) {
        TreeNode ans = root;
        int sum = 0; // 已访问（更大）结点值之和
        TreeNode curr = root;

        while (curr != null) {
            if (curr.right != null) {
                // 后继：右子树一路向左
                TreeNode prev = curr.right;
                while (prev.left != null && prev.left != curr) {
                    prev = prev.left;
                }
                if (prev.left == null) {
                    prev.left = curr; // 建线索，先走右
                    curr = curr.right;
                    continue;
                }
                prev.left = null; // 第二次到达：拆线索
            }
            // 反中序访问：先累加再写回
            sum += curr.val;
            curr.val = sum;
            curr = curr.left;
        }
        return ans;
    }
}

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(n, k, 1, new ArrayList<>(), ans);
        return ans;
    }

    // start：本层枚举起点；path：当前已选数字
    private void dfs(int n, int k, int start, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == k) {
            ans.add(new ArrayList<>(path));
            return;
        }
        // 剪枝：剩余位置不够凑满 k 个则停止
        int need = k - path.size();
        for (int i = start; i <= n - need + 1; i++) {
            path.add(i);
            dfs(n, k, i + 1, path, ans); // 下一层从 i+1 起，避免重复组合
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(1, k, n, new ArrayList<>(), ans);
        return ans;
    }

    // start：本层枚举起点；remain：还差多少凑到 n
    private void dfs(int start, int k, int remain, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == k) {
            if (remain == 0) {
                ans.add(new ArrayList<>(path));
            }
            return;
        }
        int need = k - path.size();
        // i 最大：后面还要留 need-1 个比 i 大的数，且 i 不能超过 remain
        for (int i = start; i <= 9 - need + 1; i++) {
            if (i > remain) {
                break; // 数字递增，后面更大
            }
            path.add(i);
            dfs(i + 1, k, remain - i, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    // mapping[d]：数字 d 对应字母；0、1 占位
    private static final String[] MAPPING = {
            "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
    };

    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.isEmpty()) {
            return ans;
        }
        dfs(digits, 0, new StringBuilder(), ans);
        return ans;
    }

    // index：正在处理第几位；sb：当前字母路径
    private void dfs(String digits, int index, StringBuilder sb, List<String> ans) {
        if (index == digits.length()) {
            ans.add(sb.toString());
            return;
        }
        String letters = MAPPING[digits.charAt(index) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            sb.append(letters.charAt(i));
            dfs(digits, index + 1, sb, ans);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates); // 便于按 remain 剪枝
        dfs(candidates, 0, target, new ArrayList<>(), ans);
        return ans;
    }

    // start：本层枚举起点；remain：还差多少凑到 target
    private void dfs(int[] candidates, int start, int remain,
                     List<Integer> path, List<List<Integer>> ans) {
        if (remain == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) {
                break; // 后面更大，无需再试
            }
            path.add(candidates[i]);
            // 传 i：同一数字可再用；不回头选更小下标，防重复组合
            dfs(candidates, i, remain - candidates[i], path, ans);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, 0, target, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int[] candidates, int start, int remain,
                     List<Integer> path, List<List<Integer>> ans) {
        if (remain == 0) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) {
                break; // 已排序，后面更大
            }
            // 同层去重：相同值只让第一个分支出去，避免 [1a,2] 与 [1b,2] 重复
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(candidates[i]);
            dfs(candidates, i + 1, remain - candidates[i], path, ans); // i+1：每个数只用一次
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    public List<List<String>> partition(String s) {
        int n = s.length();
        boolean[][] isPal = new boolean[n][n]; // isPal[i][j]：s[i..j] 是否回文
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j < n; j++) {
                isPal[i][j] = s.charAt(i) == s.charAt(j)
                        && (j - i <= 1 || isPal[i + 1][j - 1]);
            }
        }

        List<List<String>> ans = new ArrayList<>();
        dfs(s, 0, isPal, new ArrayList<>(), ans);
        return ans;
    }

    // start：s[0..start) 已切好
    private void dfs(String s, int start, boolean[][] isPal,
                     List<String> path, List<List<String>> ans) {
        if (start == s.length()) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) {
            if (!isPal[start][end]) {
                continue; // 本段不是回文，不能切在这里
            }
            path.add(s.substring(start, end + 1));
            dfs(s, end + 1, isPal, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> ans = new ArrayList<>();
        dfs(s, 0, 0, new StringBuilder(), ans);
        return ans;
    }

    // idx：下一段起始下标；seg：已切段数 0..4
    private void dfs(String s, int idx, int seg, StringBuilder sb, List<String> ans) {
        if (seg == 4) {
            if (idx == s.length()) {
                ans.add(sb.toString());
            }
            return;
        }
        int remain = s.length() - idx;
        int need = 4 - seg;
        if (remain < need || remain > 3 * need) {
            return; // 剩下的字符填不满 / 塞不下剩余段
        }
        int maxLen = Math.min(3, remain);
        for (int len = 1; len <= maxLen; len++) {
            if (!valid(s, idx, idx + len - 1)) {
                continue;
            }
            int old = sb.length();
            if (seg > 0) {
                sb.append('.');
            }
            sb.append(s, idx, idx + len);
            dfs(s, idx + len, seg + 1, sb, ans);
            sb.setLength(old); // 一次撤销点和数字
        }
    }

    // s[l..r] 闭区间是否为合法 IP 段
    private boolean valid(String s, int l, int r) {
        int len = r - l + 1;
        if (len > 1 && s.charAt(l) == '0') {
            return false; // 前导零
        }
        int val = 0;
        for (int i = l; i <= r; i++) {
            val = val * 10 + (s.charAt(i) - '0');
        }
        return val <= 255;
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), ans);
        return ans;
    }

    // index：本层从 nums[index] 起向后选
    private void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(path)); // 进入即收集：当前 path 已是一个子集
        for (int i = index; i < nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i + 1, path, ans); // 后面只能选更大下标，避免 [1,2] 与 [2,1]
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums); // 相同值相邻
        List<List<Integer>> ans = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int[] nums, int index, List<Integer> path, List<List<Integer>> ans) {
        ans.add(new ArrayList<>(path));
        for (int i = index; i < nums.length; i++) {
            // 同层去重：本层已经用过 nums[i-1]，跳过相同的 nums[i]
            if (i > index && nums[i] == nums[i - 1]) {
                continue;
            }
            path.add(nums[i]);
            dfs(nums, i + 1, path, ans);
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        boolean[] used = new boolean[nums.length]; // used[i]：nums[i] 是否已在路径中
        dfs(nums, used, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue; // 本排列里已用过该下标
            }
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        Arrays.sort(nums); // 相同值相邻，便于同层去重
        boolean[] used = new boolean[nums.length];
        dfs(nums, used, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int[] nums, boolean[] used, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            // 同层去重：相同值只让「左边那个」先被选；used[i-1]==false 说明 i-1 在本层刚被撤销
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used, path, ans);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> ans = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], '.');
        }
        boolean[] col = new boolean[n];
        boolean[] diag = new boolean[2 * n];     // 主对角：row - col + n
        boolean[] anti = new boolean[2 * n - 1]; // 副对角：row + col
        dfs(board, 0, n, col, diag, anti, ans);
        return ans;
    }

    private void dfs(char[][] board, int row, int n, boolean[] col, boolean[] diag,
                     boolean[] anti, List<List<String>> ans) {
        if (row == n) {
            List<String> plan = new ArrayList<>(n);
            for (char[] r : board) {
                plan.add(new String(r));
            }
            ans.add(plan);
            return; // 必须返回，否则 row==n 还会去改 board[n]
        }
        for (int j = 0; j < n; j++) {
            int d = row - j + n;
            int a = row + j;
            if (col[j] || diag[d] || anti[a]) {
                continue;
            }
            col[j] = diag[d] = anti[a] = true;
            board[row][j] = 'Q';
            dfs(board, row + 1, n, col, diag, anti, ans);
            board[row][j] = '.';
            col[j] = diag[d] = anti[a] = false;
        }
    }
}

class Solution {
    public void solveSudoku(char[][] board) {
        boolean[][] row = new boolean[9][10]; // row[i][d]：第 i 行是否已有数字 d
        boolean[][] col = new boolean[9][10];
        boolean[][] box = new boolean[9][10]; // 九宫：从上到下、从左到右编号 0..8
        List<int[]> blanks = new ArrayList<>();

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    blanks.add(new int[] { i, j });
                    continue;
                }
                int d = board[i][j] - '0';
                row[i][d] = col[j][d] = box[i / 3 * 3 + j / 3][d] = true;
            }
        }
        dfs(board, 0, blanks, row, col, box);
    }

    // k：正在填 blanks 的第 k 个空格；成功则 true（唯一解，找到即停）
    private boolean dfs(char[][] board, int k, List<int[]> blanks,
                        boolean[][] row, boolean[][] col, boolean[][] box) {
        if (k == blanks.size()) {
            return true;
        }
        int r = blanks.get(k)[0];
        int c = blanks.get(k)[1];
        int b = r / 3 * 3 + c / 3;
        for (int d = 1; d <= 9; d++) {
            if (row[r][d] || col[c][d] || box[b][d]) {
                continue;
            }
            board[r][c] = (char) ('0' + d);
            row[r][d] = col[c][d] = box[b][d] = true;
            if (dfs(board, k + 1, blanks, row, col, box)) {
                return true; // 后面都填好了，不再撤销
            }
            board[r][c] = '.';
            row[r][d] = col[c][d] = box[b][d] = false;
        }
        return false; // 1-9 都不行，回溯给上一格改数
    }
}

class Solution {
    public List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(nums, 0, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> ans) {
        if (path.size() >= 2) {
            ans.add(new ArrayList<>(path)); // 至少两个才合法，进入后先收集再继续加
        }
        boolean[] used = new boolean[201]; // 仅本层：used[x+100] 表示值 x 是否已选过
        for (int i = start; i < nums.length; i++) {
            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1)) {
                continue; // 不能破坏非递减
            }
            if (used[nums[i] + 100]) {
                continue; // 同层相同值只走一次，避免 [4,7a] 与 [4,7b] 重复
            }
            used[nums[i] + 100] = true;
            path.add(nums[i]);
            dfs(nums, i + 1, path, ans); // 子序列：后面只能用更大下标
            path.remove(path.size() - 1);
        }
    }
}

class Solution {
    public List<String> findItinerary(List<List<String>> tickets) {
        Map<String, PriorityQueue<String>> graph = new HashMap<>();
        for (List<String> t : tickets) {
            graph.computeIfAbsent(t.get(0), k -> new PriorityQueue<>()).offer(t.get(1));
        }
        LinkedList<String> ans = new LinkedList<>();
        dfs("JFK", graph, ans); // 题目规定从 JFK 出发
        return ans;
    }

    private void dfs(String from, Map<String, PriorityQueue<String>> graph, LinkedList<String> ans) {
        PriorityQueue<String> dests = graph.get(from);
        // 先把当前机场所有未用机票走完（死胡同留到最后再入结果）
        while (dests != null && !dests.isEmpty()) {
            dfs(dests.poll(), graph, ans); // poll：用掉字典序最小的一张
        }
        ans.addFirst(from); // 后序插入：先走完的点排在后面
    }
}

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g); // 胃口从小到大
        Arrays.sort(s); // 饼干从小到大
        int ans = 0;
        int j = 0; // 当前尝试的饼干下标
        for (int i = 0; i < g.length; i++) {
            // 找第一块能喂饱 g[i] 的饼干
            while (j < s.length && s[j] < g[i]) {
                j++;
            }
            if (j == s.length) {
                break; // 饼干不够了
            }
            ans++;
            j++; // 这块饼干已用，下一块
        }
        return ans;
    }
}

class Solution {
    public int wiggleMaxLength(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return n;
        }
        int prevDiff = 0; // 上一次计入摆动的差值；0 表示尚未形成方向
        int ans = 1; // 至少保留一个数
        for (int i = 1; i < n; i++) {
            int diff = nums[i] - nums[i - 1];
            // 出现新的峰/谷：与上一段方向相反；prevDiff==0 时第一次非零差也算
            if ((diff > 0 && prevDiff <= 0) || (diff < 0 && prevDiff >= 0)) {
                ans++;
                prevDiff = diff; // 平坡（diff==0）不更新，继续等真正转向
            }
        }
        return ans;
    }
}

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE; // 全局最大子数组和
        int preSum = 0; // 以当前下标结尾的最大连续和
        for (int num : nums) {
            // 前缀已为负：丢弃，从当前数重新开一段
            preSum = preSum < 0 ? num : preSum + num;
            ans = Math.max(ans, preSum);
        }
        return ans;
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for (int i = 1; i < prices.length; i++) {
            // 上涨就卖：等价于把每一段正收益都收入囊中
            if (prices[i] > prices[i - 1]) {
                ans += prices[i] - prices[i - 1];
            }
        }
        return ans;
    }
}

class Solution {
    public boolean canJump(int[] nums) {
        int maxRight = 0; // 当前能跳到的最远下标
        for (int i = 0; i < nums.length; i++) {
            maxRight = Math.max(maxRight, i + nums[i]); // 在 i 处起跳能到的最远
            if (maxRight >= nums.length - 1) {
                return true; // 已覆盖终点
            }
            if (i >= maxRight) {
                return false; // 最远就卡在 i（通常 nums[i]==0），无法再前进
            }
        }
        return true;
    }
}

class Solution {
    public int jump(int[] nums) {
        int ans = 0; // 最少跳跃次数
        int maxReach = 0; // 当前跳覆盖范围内，再起跳能到的最远下标
        int end = 0; // 当前这一跳的右边界
        int n = nums.length;
        // 不访问最后一个下标：若已能覆盖终点，不必从终点再起跳
        for (int i = 0; i < n - 1; i++) {
            maxReach = Math.max(maxReach, i + nums[i]);
            if (i == end) {
                // 本跳区间扫完，必须再跳一次
                ans++;
                end = maxReach;
                if (end >= n - 1) {
                    return ans; // 新边界已盖过终点
                }
            }
        }
        return ans;
    }
}

class Solution {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums); // 负数在前，从小到大翻最亏的负数
        int ans = 0;
        int min = Integer.MAX_VALUE; // 翻完后数组中的最小值（用于剩余奇数次）
        for (int num : nums) {
            if (num < 0 && k > 0) {
                num = -num; // 把负数变成正
                k--;
            }
            ans += num;
            min = Math.min(min, num);
        }
        // 负数不够翻：剩余 k 次；偶次等价于不改，奇次再翻一次最小值
        if (k > 0 && k % 2 == 1) {
            ans -= 2 * min;
        }
        return ans;
    }
}

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0; // 前缀和：从 0 走到 i 的净油量累计
        int min = 0; // 前缀和最小值
        int ans = 0; // 最低点下一位，即候选起点
        for (int i = 0; i < gas.length; i++) {
            sum += gas[i] - cost[i];
            if (sum < min) {
                min = sum;
                ans = (i + 1) % gas.length; // 最低点之后重新出发
            }
        }
        return sum < 0 ? -1 : ans; // 总油不够则无解
    }
}

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        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;
            }
        }

        int ans = candies[n - 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);
            }
            ans += candies[i];
        }
        return ans;
    }
}

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0; // 手头 5 元张数
        int ten = 0;  // 手头 10 元张数
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false; // 找不出 5
                }
                five--;
                ten++;
            } else { // 20：找 15
                if (ten > 0 && five > 0) {
                    ten--;
                    five--; // 优先 10+5，多留 5 给后面
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        // 身高降序；同身高按 k 升序（k 小的更靠前）
        Arrays.sort(people, (a, b) -> a[0] != b[0] ? b[0] - a[0] : a[1] - b[1]);
        List<int[]> queue = new LinkedList<>(); // 中间插入方便
        for (int[] person : people) {
            // person[1] 即 k：前面应有 k 个更高或等高的人；此时队中全是更高/等高，插到下标 k
            queue.add(person[1], person);
        }
        return queue.toArray(new int[people.length][]);
    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, Comparator.comparingInt(p -> p[1])); // 右端点升序
        int ans = 0;
        long pre = Long.MIN_VALUE; // 上一支箭的位置；用 long 防 MIN_VALUE 边界
        for (int[] p : points) {
            if (p[0] > pre) {
                // 当前气球左端已超过上支箭，必须再射
                ans++;
                pre = p[1]; // 射在右端点，尽量多覆盖后面气球
            }
            // 否则 p[0] <= pre <= p[1]，已被上支箭炸掉
        }
        return ans;
    }
}

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1])); // 按右端点升序
        int ans = 0; // 删除个数
        int prevEnd = Integer.MIN_VALUE; // 上一个保留区间的右端点
        for (int[] interval : intervals) {
            if (interval[0] >= prevEnd) {
                // 不重叠（含端点相接），保留
                prevEnd = interval[1];
            } else {
                ans++; // 与上一段重叠，删掉结束更晚的（当前）
            }
        }
        return ans;
    }
}

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

class Solution {
    public List<Integer> partitionLabels(String s) {
        int[] lastIndex = new int[26]; // 字母最后一次出现的下标
        for (int i = 0; i < s.length(); i++) {
            lastIndex[s.charAt(i) - 'a'] = i;
        }

        List<Integer> ans = new ArrayList<>();
        int maxReach = 0; // 当前片段必须延伸到的最右下标
        int left = 0;     // 当前片段左端
        for (int i = 0; i < s.length(); i++) {
            maxReach = Math.max(maxReach, lastIndex[s.charAt(i) - 'a']);
            if (i == maxReach) {
                // 走到本片段右端：中间出现过的字母都不会再出现在后面
                ans.add(i - left + 1);
                left = i + 1;
            }
        }
        return ans;
    }
}

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0])); // 左端升序
        List<int[]> ans = new ArrayList<>();
        ans.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            int[] last = ans.get(ans.size() - 1);
            if (last[1] >= intervals[i][0]) {
                // 重叠或相接：合并右端
                last[1] = Math.max(last[1], intervals[i][1]);
            } else {
                ans.add(intervals[i]);
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int nineFrom = s.length; // 从这个下标开始全部填 9
        for (int i = s.length - 1; i > 0; i--) {
            if (s[i] < s[i - 1]) {
                s[i - 1]--;      // 前一位减一，后面用 9 补满
                nineFrom = i;    // 不断左移：最终填 9 的起点是最左一次违规
            }
        }
        for (int i = nineFrom; i < s.length; i++) {
            s[i] = '9';
        }
        return Integer.parseInt(new String(s));
    }
}

class Solution {
    private int ans;

    public int minCameraCover(TreeNode root) {
        ans = 0;
        // 根仍未覆盖时，必须在根上再放一台
        if (dfs(root) == 0) {
            ans++;
        }
        return ans;
    }

    /**
     * @return 0 未覆盖；1 本结点有摄像头；2 已被覆盖（无摄像头）
     */
    private int dfs(TreeNode node) {
        if (node == null) {
            return 2; // 空结点视为「已覆盖」，不影响父结点决策
        }
        int left = dfs(node.left);
        int right = dfs(node.right);

        // 左右孩子都已被覆盖：本结点暂不放，留给父结点覆盖
        if (left == 2 && right == 2) {
            return 0;
        }
        // 有孩子未覆盖：本结点必须放摄像头
        if (left == 0 || right == 0) {
            ans++;
            return 1;
        }
        // 其余：至少一个孩子有摄像头，本结点已被覆盖
        // （left/right 为 1 或 2，且不是「双 2」——双 2 已在上面返回）
        return 2;
    }
}