题目陈述

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

算法一:

算法思路

  • 不难发现,二叉搜索树(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为节点数量
  • 空间复杂度,定义了两个辅助指针,故为