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

/*
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 == NULL) return NULL;
        pRootOfTree->left = Convert_sub(pRootOfTree->left,1);
        if(pRootOfTree->left)  pRootOfTree->left->right = pRootOfTree; //指向后继
        pRootOfTree->right = Convert_sub(pRootOfTree->right,2);
        if( pRootOfTree->right) pRootOfTree->right->left = pRootOfTree; //指向前驱
        
        TreeNode* head = pRootOfTree;
        while(head->left){
            head = head->left;
        }
        return head;
    }
    
    TreeNode* Convert_sub(TreeNode* pRootOfTree,int lr) {
        if(pRootOfTree == NULL) return NULL;

        if(pRootOfTree->left){
            pRootOfTree->left = Convert_sub(pRootOfTree->left,1);
            pRootOfTree->left->right = pRootOfTree; //指向后继
        }
        
        if(pRootOfTree->right){
           pRootOfTree->right = Convert_sub(pRootOfTree->right,2);
           pRootOfTree->right->left = pRootOfTree; //指向前驱
        }
        
        if(lr == 1)
            return pRootOfTree->right== NULL ? pRootOfTree: pRootOfTree->right;
        else
            return pRootOfTree->left == NULL ? pRootOfTree: pRootOfTree->left;
    }
    
};