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

typedef struct TreeNode Node;

Node* Convert_core(Node* pHead) {

    Node* pNode = pHead;
    Node* left=NULL;
    Node* right=NULL;
    Node* ret;
    if (!pNode)
        return NULL;

    if (pNode->left)
    {
        left = pNode->left;
        while (left->right)
            left = left->right;
    }
        
    
    ret = pNode;
    while (ret->left)
        ret = ret->left;
    Convert_core(pNode->left);

    if (left)
    {
        pNode->left = left;
        left->right = pNode;
    }
    
    if (pNode->right)
    {
        right = pNode->right;
        while (right->left)
            right = right->left;
    }
    Convert_core(pNode->right);
        
    if (right)
    {
        pNode->right = right;
        right->left = pNode;
    }
    return ret;
}


struct TreeNode* Convert(struct TreeNode* pRootOfTree ) {
    if (!pRootOfTree)
        return NULL;
    return Convert_core(pRootOfTree);
}