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

/*
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;
		}
		if (pRootOfTree->left==nullptr&&pRootOfTree->right==nullptr) {
			return pRootOfTree;
		}
		//得到左子树序列的头结点
		TreeNode* left=Convert(pRootOfTree->left);
		TreeNode* p=left;
		//得到左子树的尾结点
		while (p!=nullptr&&p->right!=nullptr) {
			p=p->right;
		}
		//如果有左子树节点，则要连接根节点
		if (left!=nullptr) {
			p->right=pRootOfTree;
			pRootOfTree->left=p;
		}
		//同理拿到右子树头结点，不为空则连接根节点
		TreeNode* Right=Convert(pRootOfTree->right);
		if (Right!=nullptr) {
			Right->left=pRootOfTree;
			pRootOfTree->right=Right;
			
		}
		return left!=nullptr?left:pRootOfTree;
    }
};