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

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 *leftNode = Convert(pRootOfTree->left);
        TreeNode *curNode = leftNode;
        //找到左子树最右边的叶子节点
        while(curNode != nullptr && curNode->right != nullptr) {
            curNode = curNode->right;
        }
        //连接根节点与左子树的最右叶子节点
        if(leftNode != nullptr) {
            pRootOfTree->left = curNode;
            curNode->right = pRootOfTree;
        }
        
        //右子树的最左叶子节点
        TreeNode *rightNode = Convert(pRootOfTree->right);
        //连接根节点与右子树的最左叶子节点
        if(rightNode != nullptr) {
            pRootOfTree->right = rightNode;
            rightNode->left = pRootOfTree;
        }
        //考虑没有左子树的情况
        return leftNode==nullptr?pRootOfTree:leftNode;
    }
};