题目陈述

大意：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表

算法一：

算法思路

• 不难发现，二叉搜索树（BST）的中序遍历，得到的序列，是递增的
• 而需要的双向链表也就是利用递增序列排序的
• 因为STL中的vector是个模板类，也就是说他不仅仅可以装整数和字符，还可以装任意类型的，所以我们就用vector来装指针
• 然后依次连接vector中的前后指针即可

  代码实现

  vector<TreeNode*> v;//将节点指针直接放入vector中，以便于直接访问 
  class Solution {
    public:
        void inOrder(TreeNode* p) {//中序遍历BST得到的序列就是递增的序列 
            if(p==NULL)return;
            inOrder(p->left);//递归左子树 
            v.push_back(p);//将指针放入v中 
            inOrder(p->right);//递归右子树 
            return ;
        }
        TreeNode* Convert(TreeNode* rt) {
            TreeNode* head=NULL;//双向链表的头 
            inOrder(rt);//中序遍历 
            int len=v.size();//节点个数 
            if(len) {
                head=v[0];
                v[0]->left=NULL;//第一个节点没有先驱 
                if(len>1)v[0]->right=v[1];//元素超过两个，头才有右指针 
                for(int i=1; i<len-1; i++) {
                    v[i]->left=v[i-1];//左指针指向前面那个节点 
                    v[i]->right=v[i+1];//右指针指向后面那个数 
                }
                if(len>1)v[len-1]->left=v[len-2];//元素超过两个，尾才有左指针 
                v[len-1]->right=NULL;//最后一个元素，没有后继 
            }
            return head;//返回双向链表的头指针 
        }
  };

  复杂度分析

• 时间复杂度O(n)，n为BST的节点数，中序遍历一次为O(n),连接成双向链表为O(n)，所以总得为O(n)
• 空间复杂度为O(n),因为定义了一个vector数组来储存指针

  算法二：线索二叉树

  线索二叉树回顾

• 我们在《数据结构》这门课程中都学过线索二叉树（大部分人），也容易看出这就是一道线索二叉树的题目
• 当然还是有点差别的，所以我们这边从二叉树线索化的过程中寻找启发
• 我们先来回顾一下，线索二叉树的结构
  
• 所以我们就得到了线索二叉树节点的结构体定义，如下：
  
• 我们定义了p、和pre指针，其中p指向当前节点，pre指向刚刚访问的节点
  

  中序序列的性质

• 中序遍历：左--根--右
• 我们可以从中序遍历的结构中得到，如果节点没有左儿子，那么中序序列中，他前面的那个字母，就是当前最晚且已经遍历完左子树的节点（如果有的话，否则就是NULL）
• 同理，如果当前节点没有右儿子的话，那么在中序序列中，他的后面一个字母，就是接下来最晚且已经遍历完左子树的节点
• 所以我们就可以知道，各个节点的前驱后继的关系了
• 下面我们动画演示线索化二叉树的过程

  线索化二叉树模板

• 注意：以下不是本题代码，只是线索化二叉树的模板
• 怕有同学没认真看，误解了，所以我直接用图片的形式了
  
  

动画演示

中序线索化演示

算法思路

• 显然我们只需要在上述代码上面做一些变换，即可得到双向链表
• 首先，我们不需要这样的标记
• 其次，我们需要建立双向的指针
• 最后，我们要返回的答案是中序遍历最左端的节点

  代码实现

  C++

  class Solution
  {
  public:
    TreeNode *pre = NULL,*ans=NULL;//pre含义同上述图片代码，ans为双向链表表头
    TreeNode *Convert(TreeNode *p)
    { 
        inOrder(p);//中序遍历，线索化二叉树
        return ans;//返回答案,，最左端的节点，为双向链表的表头
    }
    void inOrder(TreeNode *p){
        if(p==NULL)return;//如果是空树的情况
        inOrder(p->left);//递归调用，左子树线索化
        if (p->left == NULL)//同上述图片中的代码，前驱线索化
        {
            if(ans==NULL)ans=p;//第一个找到的左子树为空的节点，为双向链表的表头
            //答案即中序遍历最左端的节点
            p->left = pre;//前驱线索化
            if(pre!=NULL){//如果前驱节点存在
                pre->right=p;//因为链表是双向的，建立前驱节点的后继线索
            }
        }
        if (pre != NULL && pre->right == NULL)//同上述图片中的代码，后继线索化
        {
            pre->right = p;//建立前驱节点的后继线索
            p->left = pre;//建立后继节点的前驱线索
        }
        pre=p;
        inOrder(p->right);//递归调用，右子树线索化
        return ;//返回
    }
  };

  Python3

  class Solution:
    def Convert(self , p):
        self.pre=None  #pre含义同上述图片代码
        self.ans=None  #ans为双向链表表头
        self.inOrder(p) #中序遍历，线索化二叉树
        return self.ans #返回答案,，最左端的节点，为双向链表的表头
    def inOrder(self,p): #中序遍历
        if p==None: #如果是空树的情况
            return
        self.inOrder(p.left)#递归调用，左子树线索化
        if p.left==None:#同上述图片中的代码，前驱线索化
            if self.ans==None:#第一个找到的左子树为空的节点，为双向链表的表头
                self.ans=p#答案即中序遍历最左端的节点
            p.left=self.pre#前驱线索化
            if self.pre!=None:#如果前驱节点存在
                self.pre.right=p#因为链表是双向的，建立前驱节点的后继线索
        if self.pre!=None and self.pre.right==None:#同上述图片中的代码，后继线索化
            self.pre.right=p#建立前驱节点的后继线索
            p.left=self.pre#建立后继节点的前驱线索
        self.pre=p
        self.inOrder(p.right)#递归调用，右子树线索化

复杂度分析

• 时间复杂度，中序遍历一遍二叉树，每个节点都只被访问了一次，故时间复杂度为，n为节点数量
• 空间复杂度，定义了两个辅助指针，故为