一、问题描述

输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中，不能创建任何新的结点，只能调整树中的结点指针的指向来实现。

二、实现思路

在二叉搜索树中，每个结点都有两个分别指向其左、右子树的指针，左子树结点的值总是小于父结点的值，右子树结点的值总是大于父结点的值。而在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。所以这两种数据结构的结点是一致，二叉搜索树之所以为二叉搜索树，双向链表之所以为双向链表，只是因为两个指针的指向不同而已

思路：在转换成排序双向链表时，原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向下一个结点的指针。对于树的操作，通常是在遍历树的各个结点的过程中，通过对结点实施某些操作来完成的，这个算法也不例外。由于要求转换后的双向链表也是有序的，而我们从上面也可以看到，当我们以中序遍历二叉搜索树时，其遍历的结点就是有序的，所以在这里采用的遍历顺序应该是中序。

//递归#include<iostream>#include<stack>usingnamespacestd;structBinaryTreeNode{intdata;BinaryTreeNode*left;BinaryTreeNode*right;BinaryTreeNode(intx):data(x),left(NULL),right(NULL){}};classBinaryTree{protected:BinaryTreeNode*_root;BinaryTreeNode*_CreateBinaryTree(int*arr,int&index,intsize){BinaryTreeNode*root=NULL;if(index<size&&arr[index]!='#'){root=newBinaryTreeNode(arr[index]);root->left=_CreateBinaryTree(arr,++index,size);root->right=_CreateBinaryTree(arr,++index,size);}returnroot;}void_Clear(BinaryTreeNode*root){if(root==NULL)return;_Clear(root->left);_Clear(root->right);deleteroot;}void_Convert(BinaryTreeNode*root,BinaryTreeNode**head)//有可能改变head,加引用{if(root==NULL)return;BinaryTreeNode*cur=root;if(cur->left)_Convert(root->left,head);cur->left=*head;if(*head)(*head)->right=cur;*head=cur;if(cur->right)_Convert(cur->right,head);}//打印并销毁双向链表private:staticvoidPrintList(BinaryTreeNode*head){if(head==NULL)return;BinaryTreeNode*cur=head;while(cur){cout<<cur->data<<"";if(cur->left)cout<<"prev"<<cur->left->data<<"";if(cur->right)cout<<"next"<<cur->right->data<<endl;cur=cur->right;}}staticvoidDestroy(BinaryTreeNode**head){BinaryTreeNode*cur=*head;BinaryTreeNode*del=NULL;while(cur){del=cur;cur=cur->right;deletedel;}head=NULL;}public:BinaryTree():_root(NULL){}~BinaryTree(){_Clear(_root);}BinaryTree(int*arr,intsize){intindex=0;_root=_CreateBinaryTree(arr,index,size);}voidPreOrder_Non(){if(_root==NULL)return;BinaryTreeNode*cur=_root;stack<BinaryTreeNode*>s;s.push(_root);while(!s.empty()){cur=s.top();printf("%d",cur->data);s.pop();if(cur->right)s.push(cur->right);if(cur->left)s.push(cur->left);}}BinaryTreeNode*TransformList(){if(_root==NULL)returnNULL;//返回匿名对象//应按后序遍历顺序BinaryTreeNode*ret=NULL;_Convert(_root,&ret);while(ret!=NULL&&ret->left!=NULL)ret=ret->left;_root=NULL;PrintList(ret);Destroy(&ret);}};voidTest1(){intarr[]={10,6,4,'#','#',8,'#','#',14,12,'#','#',16};BinaryTreebt1(arr,sizeof(arr)/sizeof(arr[0]));bt1.PreOrder_Non();BinaryTreeNode*head=bt1.TransformList();}//非递归TreeNode*transfer(TreeNode*root){//leftwillbeusedaspreviouspointer(pointtoalittleone);//rightwillbeusedaspostpointer(pointtoalargeone);if(!root)returnNULL;Stack*s=newStack();TreeNode*curr,*head,*tail;curr=root;head=NULL,tail=NULL;while(true){while(curr){s->push(curr);curr=curr->left;}if(s->isEmpty())break;curr=s->pop();//visit(curr);//将curr节点加入到双向链表末尾if(head==NULL){//curr是链表中的第一个节点。head=curr;tail=curr;}else{tail->right=curr;curr->left=tail;tail=curr;//注意此处不能够修改tail->right指针的值，到目前为止，//当前节点的右子树还未被访问。}while(!curr->right){if(s->isEmpty())break;curr=s->pop();//visit(curr);//if(head==NULL){head=curr;tail=curr;}else{tail->right=curr;curr->left=tail;tail=curr;}}if(curr->right)curr=curr->right;elsebreak;}head->left=NULL;tail->right=NULL;deletes;returnhead;}

我们有一个变量head用来记录转换了的链表末结点，由于在惯例中，我们会返回链表的第1个结点（从1开始计数）的指针，而head指向的却是末结点，我们可以通过该指针来从尾走到头来获取第一个结点的指针，但是在这里我却没有这样做，因为它需要对每个结点都遍历一次，时间复杂度为O（n）。而是在变换前，找到二叉排序树的最左结点的指针。因为排序二叉树是有序的，最左的结点即为最小的结点，而我们的算法也不会删除或新增结点，也就是说结点的地址是不会改变的，所以最左的结点就是转换后的链表的第1个结点，其时间复杂度为O（logN）。

该算法首先从根要点一直向左走，找到最左边的结点，其时间复杂度为O(logN)，然后对二叉排序树中的每个结点遍历一次，进行指针变换，其时间复杂度为O(N)，所以总的时间复杂度为O(N)。

至于空间复杂度，由于ConvertNode函数进行递归调用，其函数有两个开参，而函数栈中的函数调用层数不会超过树高，所以其空间复杂度为O(logN)。