描述

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

数据范围：输入二叉树的节点数 0≤n≤10000≤n≤1000，二叉树中每个节点的值 0≤val≤10000≤val≤1000
要求：空间复杂度O(1)（即在原树上操作），时间复杂度O(n)

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继
2.返回链表中的第一个节点的指针
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述：

二叉树的根节点

返回值描述：

双向链表的其中一个头节点。

示例一：

输入：{10,6,14,4,8,12,16}

返回值：From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4;

说明：输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

示例二：

输入：{5,4,#,3,#,2,#,1}

返回值：From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1;

题解

树形结构的弊端是无法直接得到parent父节点的值，而题目将树型结构变成链表的本质就在于将left指向它的前一个节点，right指向它的后一个节点，指向后一个节点容易只需要通过递归找到最左节点然后一层一层让当前节点指向前一个，而要解决right指向后的问题就需要借助另一个prev指针来完成，所以我们需要重新封装一个InOrderConvert函数来解决此问题。

/*
struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
	TreeNode(int x) :
			val(x), left(NULL), right(NULL) {
	}
};*/
class Solution {
public:
	void InOrderConvert(TreeNode* root,TreeNode* &prev)
	{
		if(root==nullptr)//判空
		return;
		InOrderConvert(root->left,prev);//往左找最小，找到后返回进行下一步
		root->left=prev;//将prev赋值给最左节点的left赋值
		if(prev)
		prev->right=root;//如果prev不为空，就将prev的right指向当前节点
		prev=root;//将prev往上移
		InOrderConvert(root->right,prev);//root继续往右去找比它大的最小值
	}
    TreeNode* Convert(TreeNode* root) 
	{
		TreeNode*prev=nullptr;
		InOrderConvert(root,prev);
		TreeNode* head;
		while(root!=nullptr)
		{
			head=root;
			root=root->left;
		}
		return head;
    }
};