算法1

分类讨论

当左子树为空的时候，注意left = mid
当右子树为空的时候，注意right = mid

C++ 代码

class Solution {
public:
    pair<TreeNode*, TreeNode*> flat(TreeNode* root) {
        if (!root) {
            return {nullptr, nullptr};
        }
        if (!root->left && !root->right) {
            return {root, root};
        }    
        auto left = flat(root->left);
        auto right = flat(root->right);
        if (left.second) {
            left.second->right = root;
        }
        root->right = right.first;
        if (right.first) {
            right.first->left = root;
        }
        root->left = left.second;
        // left.first->left = nullptr;
        // right.second->right = nullptr;
        if (!left.first) {
            return {root, right.second};
        }
        if (!right.second) {
            return {left.first, root};
        }
        return {left.first, right.second};
    };

    TreeNode* convert(TreeNode* root) {
        return flat(root).first;
    }
};