题解 | #二叉搜索树与双向链表#

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
#include <utility>
class Solution {
  public:
    pair<TreeNode*, TreeNode*> convert_fun(TreeNode*
                                           pRootOfTree) { //给定树根节点，返回反转后的指向双链表的头尾节点的指针
        if (pRootOfTree == nullptr) {
            return make_pair(nullptr, nullptr);
        }
        TreeNode* head = nullptr, *end = nullptr; //反转后的双链表的头尾节点
        if (pRootOfTree->left ==
                nullptr) { //左支为空，反转后双链表的头节点为根节点
            head = pRootOfTree;
        } else {
            pair<TreeNode*, TreeNode*> left_list = convert_fun(
                    pRootOfTree->left);//左支反转后双链表的头尾节点
            left_list.second->right = pRootOfTree;  //左分支尾节点与根节点连接
            pRootOfTree->left = left_list.second;
            head = left_list.first; //反转后双链表的头节点为左支头节点
        }
        if (pRootOfTree->right ==
                nullptr) {    //右支为空，反转后双链表的尾节点为根节点
            end = pRootOfTree;
        } else {
            pair<TreeNode*, TreeNode*> right_list = convert_fun(
                    pRootOfTree->right);//右支反转后双链表的头尾节点
            right_list.first->left = pRootOfTree;   //右分支与根节点连接
            pRootOfTree->right =
                right_list.first;  //反转后双链表的尾节点为右支尾节点
            end = right_list.second;
        }
        return make_pair(head, end);
    }
    TreeNode* Convert(TreeNode* pRootOfTree) {
        pair<TreeNode*, TreeNode*> list = convert_fun(pRootOfTree);
        return list.first;
    }
};