二叉树高频

// Morris 中序遍历
List<Integer> morrisInorder(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    TreeNode cur = root, pre = null;
    while (cur != null) {
        if (cur.left == null) { res.add(cur.val); cur = cur.right; }
        else {
            pre = cur.left;
            while (pre.right != null && pre.right != cur) pre = pre.right; // 找前驱
            if (pre.right == null) { pre.right = cur; cur = cur.left; } // 建线索
            else { pre.right = null; res.add(cur.val); cur = cur.right; } // 恢复
        }
    }
    return res;
}

// 普通二叉树 LCA
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) return root; // 左右都有，当前是 LCA
    return left != null ? left : right;
}
// BST LCA：迭代按值定向
TreeNode lcaBST(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) root = root.left;
        else if (p.val > root.val && q.val > root.val) root = root.right;
        else return root;
    }
    return null;
}

List<Integer> rightSideView(TreeNode root) {
    List<Integer> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            if (i == size - 1) res.add(node.val); // 右视图：每层最后
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
    }
    return res;
}

int ans = Integer.MIN_VALUE;
int maxPathSum(TreeNode root) {
    dfs(root); return ans;
}
int dfs(TreeNode node) {
    if (node == null) return 0;
    int L = Math.max(0, dfs(node.left));  // 负贡献取 0
    int R = Math.max(0, dfs(node.right));
    ans = Math.max(ans, node.val + L + R); // 以 node 为顶点的路径
    return node.val + Math.max(L, R);      // 单侧贡献向上传
}

boolean isValidBST(TreeNode root) {
    return validate(root, null, null);
}
boolean validate(TreeNode node, Integer lo, Integer hi) {
    if (node == null) return true;
    if (lo != null && node.val <= lo) return false;
    if (hi != null && node.val >= hi) return false;
    return validate(node.left, lo, node.val) && validate(node.right, node.val, hi);
}

Map<Integer, Integer> idx;
TreeNode build(int[] pre, int preL, int preR, int inL, int inR) {
    if (preL > preR) return null;
    int rootVal = pre[preL];
    TreeNode root = new TreeNode(rootVal);
    int k = idx.get(rootVal);
    int leftSize = k - inL;
    root.left = build(pre, preL + 1, preL + leftSize, inL, k - 1);
    root.right = build(pre, preL + leftSize + 1, preR, k + 1, inR);
    return root;
}

TreeNode prev = null, head = null;
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    if (prev == null) head = node; else { prev.right = node; node.left = prev; }
    prev = node;
    inorder(node.right);
}
TreeNode treeToDoublyList(TreeNode root) {
    if (root == null) return null;
    inorder(root);
    head.left = prev; prev.right = head; // 连成循环
    return head;
}

// 递归
int maxDepth(TreeNode root) { return root == null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }
// 迭代 BFS
int maxDepthBFS(TreeNode root) {
    if (root == null) return 0;
    int depth = 0; Deque<TreeNode> q = new ArrayDeque<>(); q.offer(root);
    while (!q.isEmpty()) { int size = q.size(); depth++; for (int i = 0; i < size; i++) { TreeNode n = q.poll(); if (n.left != null) q.offer(n.left); if (n.right != null) q.offer(n.right); } }
    return depth;
}

// 每层输出：外层 while，内层用 size 分隔
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(root);
while (!q.isEmpty()) {
    int size = q.size(); // 本层节点数
    List<Integer> level = new ArrayList<>();
    for (int i = 0; i < size; i++) { TreeNode n = q.poll(); level.add(n.val); if (n.left != null) q.offer(n.left); if (n.right != null) q.offer(n.right); }
    res.add(level);
}

// 前序序列化
String serialize(TreeNode root) {
    if (root == null) return "null";
    return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}
// 反序列化：用队列按前序消费
TreeNode deserialize(Deque<String> q) {
    String s = q.poll();
    if (s.equals("null")) return null;
    TreeNode node = new TreeNode(Integer.parseInt(s));
    node.left = deserialize(q); node.right = deserialize(q);
    return node;
}

// 平衡判断：返回高度，-1 表示不平衡
int check(TreeNode node) {
    if (node == null) return 0;
    int L = check(node.left); if (L == -1) return -1;
    int R = check(node.right); if (R == -1) return -1;
    if (Math.abs(L - R) > 1) return -1;
    return Math.max(L, R) + 1;
}
// 直径：后序更新全局 maxDepth
int dfs(TreeNode node) {
    if (node == null) return 0;
    int L = dfs(node.left), R = dfs(node.right);
    diameter = Math.max(diameter, L + R); // 经过 node 的路径
    return Math.max(L, R) + 1;
}

int countNodes(TreeNode root) {
    if (root == null) return 0;
    int lh = height(root.left), rh = height(root.right);
    if (lh == rh) return (1 << lh) + countNodes(root.right); // 左子树满
    return (1 << rh) + countNodes(root.left);                 // 右子树满
}
int height(TreeNode node) { int h = 0; while (node != null) { h++; node = node.left; } return h; }

// 对称：镜像比较
boolean isMirror(TreeNode a, TreeNode b) {
    if (a == null && b == null) return true;
    if (a == null || b == null) return false;
    return a.val == b.val && isMirror(a.left, b.right) && isMirror(a.right, b.left);
}
// 翻转
TreeNode invert(TreeNode root) {
    if (root == null) return null;
    TreeNode t = root.left; root.left = root.right; root.right = t;
    invert(root.left); invert(root.right);
    return root;
}

int minDepth(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null) return minDepth(root.right) + 1; // 单侧
    if (root.right == null) return minDepth(root.left) + 1;
    return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}

void dfs(TreeNode node, int remaining, List<Integer> path, List<List<Integer>> res) {
    if (node == null) return;
    path.add(node.val);
    remaining -= node.val;
    if (node.left == null && node.right == null && remaining == 0)
        res.add(new ArrayList<>(path)); // 拷贝
    dfs(node.left, remaining, path, res);
    dfs(node.right, remaining, path, res);
    path.remove(path.size() - 1); // 撤销选择
}

// 字符串不可变方案，无需撤销
void dfs(TreeNode node, String path, List<String> res) {
    if (node == null) return;
    path += path.isEmpty() ? "" + node.val : "->" + node.val;
    if (node.left == null && node.right == null) res.add(path);
    dfs(node.left, path, res);
    dfs(node.right, path, res);
}

int widthOfBinaryTree(TreeNode root) {
    Deque<long[]> q = new ArrayDeque<>(); // {node, index}
    q.offer(new long[]{root.val, 0});
    int maxW = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        long left = q.peekFirst()[1], right = q.peekFirst()[1];
        for (int i = 0; i < size; i++) {
            long[] e = q.poll(); right = e[1];
            // 左/右孩子入队（下标 2*idx+1, 2*idx+2）
        }
        maxW = Math.max(maxW, (int)(right - left + 1));
    }
    return maxW;
}

TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else { // 找到
        if (root.left == null) return root.right;  // 无子/单子
        if (root.right == null) return root.left;
        TreeNode succ = root.right; while (succ.left != null) succ = succ.left; // 后继
        root.val = succ.val;
        root.right = deleteNode(root.right, succ.val);
    }
    return root;
}

// 倍增法 LCA：up[logN][n] 存 2^k 祖先
int lca(int u, int v) {
    if (depth[u] < depth[v]) { int t = u; u = v; v = t; }
    // 对齐深度
    for (int k = LOG - 1; k >= 0; k--) if (depth[u] - (1 << k) >= depth[v]) u = up[k][u];
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--) if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];
}

// 中序递增法
Integer prev = null;
boolean isValidBST(TreeNode root) {
    if (root == null) return true;
    if (!isValidBST(root.left)) return false;
    if (prev != null && root.val <= prev) return false; // 严格递增
    prev = root.val;
    return isValidBST(root.right);
}

TreeNode trimBST(TreeNode root, int low, int high) {
    if (root == null) return null;
    if (root.val < low) return trimBST(root.right, low, high); // 左子树全弃
    if (root.val > high) return trimBST(root.left, low, high); // 右子树全弃
    root.left = trimBST(root.left, low, high);
    root.right = trimBST(root.right, low, high);
    return root;
}