114. 二叉树展开为链表

【题目】：114. 二叉树展开为链表
这题要将一个二叉树转成单链表，且展开后的单链表应该和二叉树的先序遍历相同。
如果直接正向思考：能不能先序遍历，先处理当前节点（把当前遍历到的节点插入到单链表中），但是这样存在一个问题，此时当前节点的右孩子还没有被遍历到，这样会出现孩子丢失的情况。

考虑逆向思考：题目要求先序遍历（根左右）的结果，那能不能用后序遍历（左右根）呢？这样就不会出现孩子丢失的问题，因为当去更新当前的右指针时，已经遍历过他的右节点了。

但是如果是后序遍历的话，结点的顺序应该怎么处理呢？目前节点的顺序是和题目所求的节点顺序相反，因此可以考虑头插法。

class Solution {
public:
    TreeNode* res = nullptr;
    void help(TreeNode* root) {
        if(root == nullptr) {
            return;
        }
        // 右
        help(root->right);
        // 左
        help(root->left);
        // 根(头插法)
        root->left = nullptr;
        root->right = res;
        res = root;
    }
    void flatten(TreeNode* root) {
        help(root);
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(n)