一、题目描述

JZ26 二叉搜索树与双向链表
题目大意：输入一棵二叉搜索树, 将该二叉搜索树转换成一个排序的双向链表
注意审题：1. 要求不能创建任何新的节点, 只能原地调整树中节点指针的指向(暗示我们不能够采用先存下二叉树的所有值再重新创建链表)
2. 转化完成后树中节点的左指针要指向比它小的上一个结点, 右指针要指向比它大的下一个节点
3. 头尾指针不用连接起来, 即返回的不是双向循环链表
4. 返回链表中第一个节点的指针

二、算法（二叉树的中序遍历）

解题思路

1. 读完题目之后我们就能知道, 这道题只能使用原地算法, 而又要使链表从小到大排序, 首先一种思路是想办法将二叉树连接成一个双向链表, 然后再使用链表的原地排序算法解决, 但是这样解题就变得十分麻烦了
2. 我们再思考一下, 可以想到二叉树的中序遍历序列得到的就是一个从小到大的序列, 因此从这点入手, 结合双指针算法即可解决本题
3. 算法实现：1. 首先我们要想办法确定链表的头节点, 只要不断向左递归到最后一个节点即可确定 2. 其次我们要确定将前后两个节点连接起来的方案, 我们定义两个指针cur和pre, cur的当前节点的指针, pre是cur的前驱节点的指针, 因此只要pre不为空, 连接方案就是pre->right = cur, cur->left = pre 3. 二叉树中序遍历的顺序是左儿子->根节点->右儿子, 故我们只要按中序遍历的顺序移动pre和cur指针, 就可以将整个二叉树连接为一条双向链表

代码实现（C++11）

class Solution {
public:
    TreeNode *head, *pre;

    TreeNode* Convert(TreeNode* pRootOfTree) {
        if(pRootOfTree == nullptr) return pRootOfTree;    // 若为空树返回空指针
        pre = nullptr;    // 初始化化pre指针, 用于确定head节点
        inorder(pRootOfTree);
        return head;
    }

    void inorder(TreeNode* cur){
        if(cur == nullptr) return;    // 当前节点为空, 返回

        inorder(cur->left);    // 向左递归

        if(pre == nullptr) head = cur;    // 此时cur是最左侧的节点, 即根节点
        else{    // pre不为空, 按规定方案连接
            pre->right = cur;
            cur->left = pre;
        }
        pre = cur;  // 更新pre指针

        inorder(cur->right);    // 向右递归
    }
};

时间复杂度：O(n), 对二叉树进行了一次中序遍历, n是二叉树的节点数
空间复杂度：O(1), 只创建了常数个指针变量