题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
数据范围：输入二叉树的节点数0≤n≤1000，二叉树中每个节点的值0≤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;
说明：
输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
解题思路：
本题考察数据结构树的使用。运用中序遍历将二叉树的节点存放在vector中，再依次建立双向链表即可。
测试代码：
/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree==nullptr) return pRootOfTree; stack<TreeNode*> s; vector<TreeNode*> v; auto a=pRootOfTree; // 中序遍历 while(!(s.empty()&&a==nullptr)) { while(a!=nullptr) { s.push(a); a=a->left; } if(!s.empty()) { a=s.top(); s.pop(); v.push_back(a); a=a->right; } } // 双向链表建立 v.front()->left=nullptr; v.back()->right=nullptr; int size=v.size(); for(int i=0;i<size-1;++i) { v[i]->right=v[i+1]; v[i+1]->left=v[i]; } return v.front(); } };
