LeetCode Binary Tree Upside Down：三種翻轉二叉樹的解法對比

題目大意

給定一棵二叉樹，所有右節點要么是葉子要么為空（梳子狀）。將樹「倒過來」：原左子樹變為新樹，原根變為最右葉子，原右葉子變為左葉子。返回新根。
例：{1,2,3,4,5} → [4,5,2,null,null,3,1]。

解法一：遞歸（自底向上）

思路：遞歸翻轉左子樹，返回新根。翻轉後，原左孩子的 left 指向原右孩子，right 指向原根。原根斷開連接。

public TreeNode upsideDownBinaryTree(TreeNode root) {
    if (root == null || root.left == null) return root;
    TreeNode newRoot = upsideDownBinaryTree(root.left);
    root.left.left = root.right;  // 原右孩子 → 新左孩子
    root.left.right = root;       // 原根 → 新右孩子
    root.left = root.right = null; // 斷開原連接
    return newRoot;
}

解法二：迭代（自頂向下，O(1) 空間）

模擬遞歸過程，用三指針 parent, parentRight, cur 向左推進，逐步反轉指針。

public TreeNode upsideDownBinaryTree(TreeNode root) {
    TreeNode cur = root, parent = null, parentRight = null;
    while (cur != null) {
        TreeNode left = cur.left;
        cur.left = parentRight;   // 原父的右孩子 → 當前左孩子
        parentRight = cur.right;  // 保存當前右孩子供下一輪
        cur.right = parent;       // 原父 → 當前右孩子
        parent = cur;             // 更新父節點
        cur = left;               // 進入左子樹
    }
    return parent; // 最後一個非空 parent 即新根
}

解法三：後序遍歷轉層次構建（另類思路）

利用後序遍歷順序（左、右、根）恰好是翻轉後的層次順序。用佇列/虛擬節點逐個取出構建新樹。

private TreeNode out = null;
public TreeNode upsideDownBinaryTree(TreeNode root) {
    TreeNode dummy = new TreeNode(0);
    dummy.left = new TreeNode(0);
    out = dummy;
    postorder(root);
    return dummy.right;
}
private void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);
    postorder(root.right);
    if (out.left == null) {
        out.left = root; out.left.left = out.left.right = null;
    } else if (out.right == null) {
        out.right = root; out.right.left = out.right.right = null;
    }
    if (out.left != null && out.right != null) out = out.right;
}

對比總結

總結

本題關鍵在於識別「右子樹無分支」的特殊結構，將翻轉簡化為指針重組。三種解法體現了「遞歸→迭代優化→遍歷順序重構」的算法進階思路。