树的进阶：序列化与翻转

这类题目要求修改树的结构，或在树上填充额外信息。掌握"后序处理完再修改结构"的原则。

二叉树展开为链表（LeetCode 114）

将二叉树按前序遍历顺序展开为"右偏"链表（原地操作）。

方法：后序处理（Morris-like）

public void flatten(TreeNode root) {
    TreeNode curr = root;
    while (curr != null) {
        if (curr.left != null) {
            // 找左子树中最右节点
            TreeNode rightmost = curr.left;
            while (rightmost.right != null) rightmost = rightmost.right;
            // 把右子树接到左子树的最右节点
            rightmost.right = curr.right;
            // 左子树移到右边，左指针置 null
            curr.right = curr.left;
            curr.left = null;
        }
        curr = curr.right;
    }
}

时间 O(n)，空间 O(1)：不需要额外空间，迭代完成。

方法2：后序递归（更直观）

private TreeNode prev = null;

public void flatten(TreeNode root) {
    if (root == null) return;
    flatten(root.right);   // 先展开右子树
    flatten(root.left);    // 再展开左子树
    root.right = prev;     // 把之前展开的链表接在右边
    root.left = null;
    prev = root;
}

填充每个节点的下一个右侧节点指针（LeetCode 116/117）

116. 完美二叉树

public Node connect(Node root) {
    if (root == null) return null;
    Node leftmost = root;
    while (leftmost.left != null) {  // 每层从最左节点出发
        Node curr = leftmost;
        while (curr != null) {
            curr.left.next = curr.right;              // 同父节点的兄弟
            if (curr.next != null)
                curr.right.next = curr.next.left;    // 跨父节点的邻居
            curr = curr.next;
        }
        leftmost = leftmost.left;
    }
    return root;
}

117. 任意二叉树（带 null 子节点）

用"虚拟头节点"技巧，逐层处理：

public Node connect(Node root) {
    Node curr = root;
    while (curr != null) {
        Node dummy = new Node(0);  // 下一层的虚拟头
        Node tail = dummy;
        while (curr != null) {
            if (curr.left  != null) { tail.next = curr.left;  tail = tail.next; }
            if (curr.right != null) { tail.next = curr.right; tail = tail.next; }
            curr = curr.next;
        }
        curr = dummy.next;  // 移到下一层
    }
    return root;
}

翻转二叉树（LeetCode 226）

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

二叉树的序列化与反序列化（LeetCode 297）

用前序遍历 + 特殊标记（# 表示 null）。

// 序列化
public String serialize(TreeNode root) {
    if (root == null) return "#";
    return root.val + "," + serialize(root.left) + "," + serialize(root.right);
}

// 反序列化
public TreeNode deserialize(String data) {
    Queue<String> q = new LinkedList<>(Arrays.asList(data.split(",")));
    return build(q);
}

private TreeNode build(Queue<String> q) {
    String val = q.poll();
    if ("#".equals(val)) return null;
    TreeNode node = new TreeNode(Integer.parseInt(val));
    node.left  = build(q);
    node.right = build(q);
    return node;
}

总结