114. 二叉树展开为链表

题目链接

解题思路：

• 对于这类递归问题，采用「宏观」思考模式。
• 对于任意一个节点A，左子树先「展开为链表」，右子树再「展开为链表」，然后A节点，将左子树的结果，和右子树的结果，「串在一起」即可。
• 左子树展开为链表，所以要返回两个节点，一个是链表的头，然后是链表的尾。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    // 将head展开成链表
    pair<TreeNode*, TreeNode*> process(TreeNode *head) {
        if (head == nullptr) {
            return {nullptr, nullptr};
        }
        TreeNode *left_head = nullptr;     // 左链表的头
        TreeNode *left_tail = nullptr;     // 左链表的尾
        TreeNode *right_head = nullptr;    // 右链表的头
        TreeNode *right_tail = nullptr;    // 右链表的尾
        auto left_res = process(head->left);
        auto right_res = process(head->right);
        left_head = left_res.first;
        left_tail = left_res.second;
        right_head = right_res.first;
        right_tail = right_res.second;
        TreeNode *cur_head = head;
        TreeNode *cur_tail = head;
        if (left_head != nullptr) {
            cur_tail->right = left_head;
            cur_tail = left_tail;
            head->left = nullptr;   // 不要忘记这一句
        }
        if (right_head != nullptr) {
            cur_tail->right = right_head;
            cur_tail = right_tail;
        }
        
        return {cur_head, cur_tail};
    }

    void flatten(TreeNode* root) {
        process(root);
    }
};