114. 二叉树展开为链表

难度：🟡 Medium | 标签：树、Morris 风格 | 状态：⬜ LeetCode 链接

思路

O(1) 空间： 对每个节点，若有左子，找左子最右节点，把右子挂到那；再把左子搬到右、左置空；推进到右。

代码

class Solution {
public:
    void flatten(TreeNode* root) {
        auto* cur = root;
        while (cur) {
            if (cur->left) {
                auto* rightmost = cur->left;
                while (rightmost->right) rightmost = rightmost->right;
                rightmost->right = cur->right;
                cur->right = cur->left;
                cur->left = nullptr;
            }
            cur = cur->right;
        }
    }
};

复杂度

• 时间 O(n)（每节点最多访问 2 次）
• 空间 O(1)

易错 / 回顾

• 顺序是「前序」，所以左子整体放到右
• 递归后序版也行，但 O(h) 栈
• “left 置空” 漏写就 TLE 或错