XingHuiSama の博客

1. 算法核心思想：用栈模拟“先序遍历”

这道题要求展开的顺序和先序遍历（根 -> 左 -> 右）一模一样。如果用递归，在改变指针的时候很容易把右子树“弄丢”。为了破局，我们直接祭出栈（Stack）。

栈的特性是“先进后出（LIFO）”。为了让弹出来的顺序是“先左孩子，后右孩子”，我们在压栈的时候，必须反着来：先压入右孩子，再压入左孩子。这样一来，每次从栈顶拿到的节点，就绝对是符合先序遍历顺序的下一个节点。

2. 代码逻辑拆解

准备工作：我们派出了一个名叫 last 的指针，它就像是在修铁路的工人，永远站在已经铺好轨道的最后一节车厢上。最开始，它站在 root 上。
引擎启动：提前把 root 的左右孩子（先右后左）压入栈中，启动循环。
循环内部的三步曲：
1. 取节点与托孤：从栈顶拿出一个新节点 node，在对它动刀子之前，赶紧把它的左右孩子（先右后左）安全地压入栈中。
2. 接轨：把修路工人 last 所在的左边清空（last->left = NULL），然后把右边连向新拿出来的节点（last->right = node）。
3. 工人前移：轨道修长了一节，工人 last 必须往前走一步（last = node），等待下一次接轨。

‍

class Solution {
public:
    void flatten(TreeNode* root) {
        // 1. 边界拦截
        if (root == NULL) {
            return;
        }

        stack<TreeNode*> st;
        TreeNode* last = root; // last 用于记录刚刚串联好的上一个节点

        // 2. 初始装填：注意顺序，先压右孩子，再压左孩子！
        if (root->right != NULL) {
            st.push(root->right);
        }
        if (root->left != NULL) {
            st.push(root->left);
        }

        // 3. 栈不为空时，持续弹出并串联
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            
            // 每次弹出一个节点，立刻把它的孩子们压入栈（同样先右后左）
            if (node->right != NULL) {
                st.push(node->right);
            }
            if (node->left != NULL) {
                st.push(node->left);
            }

            // 4. 核心串联动作
            last->left = NULL;   // 题目要求：左指针必须全设为 NULL
            last->right = node;  // 把当前节点接在上一个节点的右边
            
            // 5. 履带履带往前开：last 走到当前节点，准备去接下一个
            last = node;
        }
    }
};

3. 复杂度分析

时间复杂度：O(N)。其中 N 是二叉树的节点数。每一个节点都会被精确地压入栈一次，弹出栈一次，并且改变指针的操作是 O(1) 的，因此总时间与节点数量成正比。
空间复杂度：O(N)。空间开销主要来自于栈 st。在最坏情况下（比如一棵没有右孩子、只有左孩子长长的树，或者反过来），栈内最多会存放 O(N) 个节点。

‍