二叉搜索树与双向链表（中序遍历）

/*
convert : 链表化子树，并返回头指针
last : 记录链表化的尾节点 按照中序遍历顺序赋值；
当前节点指向其前驱节点 root->left = last;
前驱节点指向当前节点  last->right = root;
*/
class Solution {
public:
    TreeNode* last = NULL;
    TreeNode* Convert(TreeNode* root) {
        if(!root) return NULL; 
        TreeNode *p = Convert(root->left);//链表化左子树并获得其头指针，为了判断返回链表化后的头指针
        root->left = last;//要加入的节点连接到，链表尾节点
        if(last) last->right = root;//链表尾节点链接要加入的节点。
        last = root;
        Convert(root->right);
        return p?p:root;
    }
};

/*
convert 输入一个二叉树根节点，将其转化为双向链表，返回其头结点
链表化左子树 last :记录的是链表的尾指针
last->right = root; //尾指针与根节点相连
root->left = last
链表化右子树
pRootOfTree->right = right;
right->left = pRootOfTree;
边界条件：
当root->left root->right 只有一个节点；
头尾指针都是其本身
当root ==NULL 时， 返回空
*/
class Solution {
public:
    TreeNode* last = NULL;
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree == NULL) return NULL;
        if(!pRootOfTree->left&&!pRootOfTree->right) {last = pRootOfTree; return pRootOfTree;}
        TreeNode* left = Convert(pRootOfTree->left);
        if(last){
            last->right = pRootOfTree;
            pRootOfTree->left = last;
        }
        last = pRootOfTree;
        TreeNode* right = Convert(pRootOfTree->right);
        if(right){
            pRootOfTree->right = right;
            right->left = pRootOfTree;
        }
        return left?left:pRootOfTree;
    }
};