输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。

一、问题描述

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

二、实现思路

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

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

//递归
#include<iostream>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
	int data;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
	BinaryTreeNode(int x)
		:data(x)
		, left(NULL)
		, right(NULL)
	{}
};
class BinaryTree
{
protected:
	BinaryTreeNode* _root;
	BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
	{
		BinaryTreeNode* root = NULL;
		if (index < size&&arr[index] != '#')
		{
			root = new BinaryTreeNode(arr[index]);
			root->left = _CreateBinaryTree(arr, ++index, size);
			root->right = _CreateBinaryTree(arr, ++index, size);
		}
		return root;
	}
	void _Clear(BinaryTreeNode* root)
	{
		if (root == NULL)
			return;
		_Clear(root->left);
		_Clear(root->right);
		delete root;
	}
	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:
	static void PrintList(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;
		}
	}
	static void Destroy(BinaryTreeNode** head)
	{
		BinaryTreeNode* cur = *head;
		BinaryTreeNode* del = NULL;
		while (cur)
		{
			del = cur;
			cur = cur->right;
			delete del;
		}
		head = NULL;
	}
public:
	BinaryTree()
		:_root(NULL)
	{}
	~BinaryTree()
	{
		_Clear(_root);
	}
	BinaryTree(int *arr, int size)
	{
		int index = 0;
		_root = _CreateBinaryTree(arr, index, size);
	}
	void PreOrder_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)
			return NULL;//返回匿名对象
		//应按后序遍历顺序
		BinaryTreeNode* ret = NULL;
		_Convert(_root, &ret);

		while (ret != NULL&&ret->left != NULL)
			ret = ret->left;
		_root = NULL;
		PrintList(ret);
		Destroy(&ret);
	}
};
void Test1()
{
	int arr[] = { 10, 6, 4, '#', '#', 8, '#', '#', 14, 12, '#', '#', 16 };
	BinaryTree bt1(arr, sizeof(arr) / sizeof(arr[0]));
	bt1.PreOrder_Non();
	BinaryTreeNode* head = bt1.TransformList();
}
//非递归
 TreeNode * transfer(TreeNode * root)
{
    // left will be used as previous pointer (point to a little one);
    // right will be used as post pointer (point to a large one);
    if (!root) return NULL;
    Stack *s = new Stack();
    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;
        else break;
    }

    head->left = NULL;
    tail->right = NULL;
    delete s;
    return head;
}

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

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

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