递归思想

通常来说常规思路是通过中序遍历将节点保存下来，这里提供一种递归合并链表的解题思路：递归左右子树，遍历左子树到最后一个节点lastNo，随后将left list root right list拼接起来即可

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if (pRootOfTree==NULL)
        {
            return NULL;
        }
        auto left = Convert(pRootOfTree->left);
        auto right = Convert(pRootOfTree->right);
        auto lastNode = findLastNode(left);
        if(lastNode==NULL){
            left = pRootOfTree;
        }
        else
        {
            pRootOfTree->left = lastNode;
            lastNode->right = pRootOfTree;    
        }
        if (right==NULL)
        {
            pRootOfTree->right = NULL;
            return left;
        }
        pRootOfTree->right = right;
        right->left = pRootOfTree;
        return left;
    }

    TreeNode* findLastNode(TreeNode* head)
    {
        if(head==NULL)
        {
            return NULL;
        }
        auto cursor = head;
        while(cursor->right!=NULL)
        {
            cursor = cursor->right;
        }
        return cursor;
    }
};