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

思路： 题目中所给的关键信息：

• 这是一颗二叉搜索树，中序遍历便是从小到大的排序
• 不能添加新的结点，要在原结点基础上添加链表链接 *故采用二叉树中序遍历法遍历全树，依次添加链接，创建两个指针，一个指向题目中要求的链表头（head），一个指向当前遍历的前一结点（pre)。

方法一：递归中序遍历 具体做法：首先递归到最左，初始化head与pre，然后往后遍历整棵树，依次连接pre与当前结点，并更新pre。

class Solution {
public:
    TreeNode* head = NULL;  //返回的第一个指针，即为最小值，先定为null
    TreeNode* pre = NULL;   //中序遍历当前值的上一位，初值为最小值，先定为null
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree == NULL)
            return NULL;        //中序递归，叶子为空则返回
        Convert(pRootOfTree->left); //首先递归到最左最小值
        if(pre == NULL){       //找到最小值，初始化head与pre
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        else{       //当前结点与上一结点建立连接，将pre设置为当前值
            pre->right = pRootOfTree;
            pRootOfTree->left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree->right);
        return head;
    }
};

复杂度分析

• 时间复杂度：O(n)，二叉树递归中序遍历的时间复杂度
• 空间复杂度：O(n)，递归栈所需要的最大空间

方法二：非递归中序遍历 具体做法：设置一个栈s，当二叉树遍历往左时，依次加入栈空间，当前结点为空时再弹出一个栈中的内容，处理该结点，然后进入其右结点。连接链表方式还是相同，加入一个pre与一个head指针。

class Solution {
public:
    TreeNode* Convert(TreeNode* pRootOfTree) {
        if (pRootOfTree == NULL) {
            return NULL;
        }
        stack<TreeNode*> s; //设置栈用于遍历
        TreeNode* head = NULL;
        TreeNode* pre = NULL;
        bool isFirst = true; //确认第一个遍历到最左，即为首位
        while (pRootOfTree != NULL || !s.empty()) {
            while (pRootOfTree != NULL) {   //直到没有左节点
                s.push(pRootOfTree);
                pRootOfTree = pRootOfTree->left;
            }
            pRootOfTree = s.top();
            s.pop();
            if (isFirst) {  //首位
                head = pRootOfTree;
                pre = head;
                isFirst = false;
            } else {          //当前结点与上一结点建立连接，将pre设置为当前值
                pre->right = pRootOfTree;
                pRootOfTree->left = pre;
                pre = pRootOfTree;
            }
            pRootOfTree = pRootOfTree->right;
        }
        return head;
    }
};

复杂度分析：

• 时间复杂度：O(n),遍历栈与二叉树
• 空间复杂度：O(n),栈s最大为n