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

递归分析： 递归左子树，递归返回时左子树自然成双向链表，如图，4的左子树将变成1-2-3，当然4的左孩子还是2，

这时只要顺着2向链表的右边找到最后一个结点3将是4在链表中的直接前驱。

右子树操作与左子树对称

class Solution {
public:
    TreeNode *searchDlistLast(TreeNode *p)
    {
        if (!p)
        {
            return NULL;
        }
        
        while (p->right)
        {
            p = p->right;
        }
        
        return p;
    }
    
    TreeNode *searchDlistFirst(TreeNode *p)
    {
        if (!p)
        {
            return NULL;
        }
        
        while (p->left)
        {
            p = p->left;
        }
        
        return p;
    }
    
    void dfs(TreeNode* pRoot)
    {
        if (!pRoot)
        {
            return;
        }

        dfs(pRoot->left);
        TreeNode *prev = searchDlistLast(pRoot->left);
        if (prev)
        {
            prev->right = pRoot;
            pRoot->left = prev;
        }
        
        dfs(pRoot->right);
        TreeNode *next = searchDlistFirst(pRoot->right);
        if (next)
        {
            next->left = pRoot;
            pRoot->right = next;
        }
    }
    
    TreeNode* Convert(TreeNode* pRoot)
    {
        dfs(pRoot);
        return searchDlistFirst(pRoot);
    }
};