自顶向下递归法

由于中序遍历二叉树即可将搜索二叉树排序，因此我们只需要将二叉树最左端的结点记作双向列表的头，中序遍历二叉树的同时依次将结点接入双向列表的尾端，并同时更新指向列表的尾端的指针便可。列表的头尾使用类的成员变量来记录。

于是可以分析出递归三部曲：

1. 递归函数作用：中序遍历二叉树，将当前结点接入双向列表尾端并更新指向尾部的指针，返回头指针
2. 递归终止条件：当前结点为空时，返回列表的头指针
3. 下一次递归：按左中右访问结点

由于主函数和递归函数的输入一致，所以可以将递归函数合并入主函数。

class Solution {
    TreeNode* tail = nullptr; //指向列表的头
    TreeNode* head = nullptr; //指向列表的尾

public:
    TreeNode* Convert(TreeNode* pRootOfTree)
    {
        if (!pRootOfTree) //结点为空时终止递归
            return head;
        Convert(pRootOfTree->left); //递归左树
        if (!head) //将树最左端的结点记作列表的头
            head=tail=pRootOfTree;
        else //将结点接入列表的尾并更新尾指针
        {
            pRootOfTree->left=tail;
            tail->right=pRootOfTree;
            tail = pRootOfTree;
        }
        Convert(pRootOfTree->right); //递归右树
        return head; //返回列表的头
    }
};

时间复杂度：O(N) 遍历所有节点一次
空间复杂度：O(N) 当树退化成链表时，递归栈深度为N