题目：给你二叉树的根结点 root ，请你将它展开为一个单链表：

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

我的方法一：先前序排列到一个队列，然后将队列里的node前后连接起来

步骤

1. 使用迭代的方式进行前序排列，并保存一个队列中
2. 将节点从队列中依次拿出；并将前一个的节点的right指向当前这个节点；当前这个节点的left和right都置为null；
3. 最后一个节点的left和right都置为null；

边界条件

1. 当二叉树空时，直接返回null；
2. 链表的最后一个节点的left和right都要置为null；

复杂度

时间复杂度：O(n)，因为遍历每个节点，而且每个节点都会入栈两次和出栈一次，所以时O(n)，最后将一个队列的节点前后连接成一个链表，也是O(n)，所以总体是O(n)
空间复杂度：O(n)，因为使用了一个队列是O(n)，栈是O(logn)，和树的高度有关；所以总体是O(n)。

代码

class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root){
            return;
        }

        stack<ColorNode> s;
        queue<TreeNode*> q;

        s.push(ColorNode(root, false));

        while(!s.empty()) {
            ColorNode top = s.top();
            s.pop();

            if(top.walked){
                q.push(top.node);
            }else{
                if(top.node->right){
                    s.push(ColorNode(top.node->right, false));
                }
                if(top.node->left){
                    s.push(ColorNode(top.node->left, false));
                }
                top.walked = true;
                s.push(top);
            }
        }

        TreeNode* r = q.front();
        q.pop();
        r->right = r->left = nullptr;

        while(!q.empty()){
            r->right = q.front();
            r->left = nullptr;
            r = r->right;
            q.pop();
        }

        r->right = r->left = nullptr;
    }

private:
    struct ColorNode {
        bool walked = false;
        TreeNode* node = nullptr;

        ColorNode(TreeNode* node, bool walked){
            this->node = node;
            this->walked = walked;
        }
    };
};

我的方法一优化

方法

上面方法需要一个队列，导致空间复杂是O(n)，新方法不需要这个队列；
优化后，空间复杂度为O(logn)只和stack有关，stack和树的高度有关；

代码

class Solution {
public:
    void flatten(TreeNode* root) {
        if(!root){
            return;
        }

        stack<ColorNode> s;
        s.push(ColorNode(root, false));

        TreeNode* r = nullptr;

        while(!s.empty()) {
            ColorNode top = s.top();
            s.pop();

            if(top.walked){
                if(r){
                    r->right = top.node;
                    r->left = nullptr;
                    r = r->right;
                }else{
                    r = top.node;
                }
            }else{
                if(top.node->right){
                    s.push(ColorNode(top.node->right, false));
                }
                if(top.node->left){
                    s.push(ColorNode(top.node->left, false));
                }
                top.walked = true;
                s.push(top);
            }
        }
        r->right = r->left = nullptr;
    }

private:
    struct ColorNode {
        bool walked = false;
        TreeNode* node = nullptr;

        ColorNode(TreeNode* node, bool walked){
            this->node = node;
            this->walked = walked;
        }
    };
};