题目难度：中等

题目描述：

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

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

注意: 1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继 2.返回链表中的第一个节点的指针 3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构 4.你不用输出双向链表，程序会根据你的返回值自动打印输出

输入描述： 二叉树的根节点 返回值描述： 双向链表的其中一个头节点。

示例1：

输入：{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; 说明：输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。

思路1:中序遍历递归大法

时间复杂度：O(n)，空间复杂度：O(n)

class Solution {
public:
  
  	TreeNode *head = nullptr;
  	TreeNode *pre = nullptr;
  
  	TreeNode* Convert(TreeNode* pRootOfTree) {
      
      	if(!pRootOfTree) return nullptr;
      
      	Convert(pRootOfTree->left);
      
      	if(!pre) {
          	pre = pRootOfTree;
          	head = pRootOfTree;
        } else {
          	pre->right = pRootOfTree;
          	pRootOfTree->left = pre;
          	pre = pRootOfTree;
        }
      
      	Convet(pRootOfTree->right);
      
      	return head;
    }
}

思路2:栈

时间复杂度：O(n)，空间复杂度：O(n)

class Solution {
public:
  	TreeNode* Convert(TreeNode* pRootOfTree) {
      
      	if(!pRootOfTree) return nullptr;
      
      	stack<TreeNode*> stk;
      	TreeNode *head = nullptr;
      	TreeNode *pre = nullptr;
      
      	bool isFirst = true;
      
      	while (pRootOfTree || !stk.empty()) {
          
          	while (pRootOfTree) {
              	stk.push(pRootOfTree);
              	pRootOfTree = pRootOfTree->left;
            }
          
          	pRootOfTree = stk.top();
          	stk.pop();
          
          	if(isFirst) {
              	head = pRootOfTree;
              	pre = pRootOfTree;
              	isFirst = true;
            } else {
              	pre = pRootOfTree->right;
              	pRootOfTree->left = pre;
              	pre = pRootOfTree;
            }
          	pRootOfTree = pRootOfTree->right;
        }
      	return head;
    }
}

😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘😘