114. 二叉树展开为链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入： root = [1,2,5,3,4,null,6]
输出： [1,null,2,null,3,null,4,null,5,null,6]

思路一：递归拼接（先展平左右，再重接）

• 递归出口：root 为空直接返回。
• 先递归展平 root.left 与 root.right，使两侧均变成右指针链。
• 若左链存在：
• 记录 leftList = root.left、rightList = root.right。
• 沿 right 指针找到 leftList 的尾结点 tail。
• 将 root.right 指向 leftList，并将 root.left 置为 null。
• 将 tail.right 接到原来的 rightList。

复杂度： 时间 O(n^2) 最坏（退化链时 tail 查找），空间 O(h)（递归栈）。

class Solution {
    /**
     * Recursively flattens the binary tree rooted at root into a right-skewed linked list
     * in preorder order, in-place.
     */
    public void flatten(TreeNode root) {
        if (root == null) return;

        // 1) Flatten left and right subtrees
        flatten(root.left);
        flatten(root.right);

        // 2) If a left flattened list exists, splice it between root and original right list
        if (root.left != null) {
            TreeNode leftList = root.left;
            TreeNode rightList = root.right; // might be null

            // Find tail of left list (rightmost node after flatten)
            TreeNode tail = leftList;
            while (tail.right != null) {
                tail = tail.right;
            }

            // Move left list to right, nullify left
            root.right = leftList;
            root.left = null;

            // Append original right list
            tail.right = rightList;
        }
    }
}

思路二：递归返回尾结点（避免找尾的 O(n^2)）

• 定义辅助函数 flattenAndReturnTail(root)：将以 root 为根的子树原地展平，并返回展平后链表的尾结点。
• 递归处理左右子树，得到 leftTail 与 rightTail。
• 若存在左链：
  • 将 leftTail.right 指向原 root.right；
  • 将 root.right 指向 root.left，并将 root.left 置空；

返回尾结点：优先 rightTail，其次 leftTail，否则为 root 自身。
复杂度：时间 O(n)，空间 O(h)（递归栈）。

class Solution {
    /**
     * Recursively flattens the binary tree rooted at root into a right-skewed linked list
     * in preorder order, in-place. Wrapper that uses a helper returning the tail node.
     */
    public void flatten(TreeNode root) {
        flattenAndReturnTail(root);
    }

    // Returns the tail node of the flattened list rooted at 'root'
    private TreeNode flattenAndReturnTail(TreeNode root) {
        if (root == null) return null;

        // Flatten left and right subtrees and get their tails
        TreeNode leftTail = flattenAndReturnTail(root.left);
        TreeNode rightTail = flattenAndReturnTail(root.right);

        // If there is a left flattened list, splice it between root and original right list
        if (leftTail != null) {
            // Attach original right to the end of left list
            leftTail.right = root.right;
            // Move left list to right and nullify left
            root.right = root.left;
            root.left = null;
        }

        // Return the tail of the fully flattened list
        if (rightTail != null) return rightTail;
        if (leftTail != null) return leftTail;
        return root;
    }
}

思路三：逆先序（right-left-root）+ 全局 prev 指针

• 维护一个全局/成员变量 prev，表示“已经展平成链表的头结点”（在逆先序构造的当前阶段）。
• 按顺序递归访问 right → left → root：
• 回到 root 时，将 root.right 指向 prev，root.left 置为 null；
• 更新 prev = root。
• 因为先处理 right，再处理 left，能保证最终链表顺序是先序（root-left-right）；整个过程只遍历每个结点一次，时间 O(n)，递归栈空间 O(h)。

class Solution {
    // prev 指向“已经展平成链表的当前头结点”
    private TreeNode prev = null;

    /**
     * 使用逆先序（right -> left -> root）和全局 prev 指针，就地展平为先序右链。
     */
    public void flatten(TreeNode root) {
        prev = null; // 每次调用前重置
        reversePreorder(root);
    }

    private void reversePreorder(TreeNode node) {
        if (node == null) return;

        // 先处理右子树、再处理左子树
        reversePreorder(node.right);
        reversePreorder(node.left);

        // 回溯到当前节点时，接到 prev 前面，并断开左指针
        node.right = prev;
        node.left = null;
        prev = node;
    }
}

思路四：迭代栈模拟先序

• 用栈按先序遍历（root-left-right）。
• 维护一个指针 prev 指向“已连接链表的最后一个节点”。
• 每弹出当前节点 cur：
• 若 prev 不为 null，则令 prev.right = cur 且 prev.left = null，把 cur 接到链表末尾。
• 为保证先序顺序，先把 cur.right 压栈，再把 cur.left 压栈（这样左子树先被处理）。
• 更新 prev = cur。
• 遍历结束后，确保最后一个节点的 left 为 null。

class Solution {
    /**
     * Iterative preorder (root-left-right) using a stack.
     * Links nodes into a right-only list as we traverse; nullifies all left pointers.
     * Time: O(n), Space: O(n) in worst case (stack).
     */
    public void flatten(TreeNode root) {
        if (root == null) return;

        Deque<TreeNode> stack = new ArrayDeque<>();
        stack.push(root);
        TreeNode prev = null;

        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();

            if (prev != null) {
                prev.right = cur;
                prev.left = null;
            }

            // Push right first so that left is processed first (preorder)
            if (cur.right != null) stack.push(cur.right);
            if (cur.left != null) stack.push(cur.left);

            prev = cur;
        }

        // Ensure the last node's left is null
        if (prev != null) prev.left = null;
    }
}