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

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
	  //如果当前结点为空直接返回
        if(pRootOfTree==nullptr)
		{
			return nullptr;
		}
		else 
		{
			TreeNode* pre=Convert(pRootOfTree->left);//左边排序链表的起始结点
			
			TreeNode* next=Convert(pRootOfTree->right);//右边排序链表的起始结点
			
			while(pre!=nullptr&&pre->right!=nullptr)//左边移动到最后一个结点
			{
				pre=pre->right;
			}
			//连接左边中间和右边
			if(pre!=nullptr)//注意左右两边可能为空
				pre->right=pRootOfTree;
			pRootOfTree->right=next;
			if(next!=nullptr)
				next->left=pRootOfTree;
			pRootOfTree->left=pre;

		  
		  //返回排序好链表的最左边结点
			while(pRootOfTree!=nullptr&&pRootOfTree->left!=nullptr)
			{
				pRootOfTree=pRootOfTree->left;
			}
			return pRootOfTree;
		}
    }
};

使用中序递归遍历，在递归时做连接操作