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

//递归
/*
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) return nullptr;
        
        TreeNode *left    = pRootOfTree->left;
        TreeNode *right   = pRootOfTree->right;
        if (left) {
            TreeNode *lr = Convert(left);    //获取左子树转换链表的左边节点
            while (lr->right) lr = lr->right;    //获得左子树的右边节点
            lr->right = pRootOfTree;
            pRootOfTree->left = lr;
            while (left->left) left = left->left;    //left遍历为双链表最左边节点
        }
        if (right) {
            TreeNode *rl = Convert(right);    //获取右子树转换链表的左边节点
            pRootOfTree->right = rl;
            rl->left = pRootOfTree;
        }
        
        if (left) return left;
        
        return pRootOfTree;
    }
};