宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取

题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

题目分析
这道题怎么说呢，牛客标它的难度是最低的这我是不太认同的。首先从题目描述来看，不读个3、4遍可能不知道它是什么意思，同时又考察了链表和二叉树这两种结构。嗯不知道牛客难度标记是不是越小越不好做，很魔性。

正题：
先来看一棵简单的二叉搜索树
牛客——二叉搜索树与双向链表-编程部落
由他变成一个有序的双向链表还是比较简单的。如下图：
牛客——二叉搜索树与双向链表-编程部落
接下来升级二叉搜索树的复杂程度
牛客——二叉搜索树与双向链表-编程部落
他怎么变呢？先变简单的把它的子树先转成链表
牛客——二叉搜索树与双向链表-编程部落
接下来改变根节点的指针指向，把它链到3、5中间
牛客——二叉搜索树与双向链表-编程部落
到这里我们基本上可以这道题要采用什么方法了，还是树的常用操作——递归。但是每次做些什么？
一个节点和三个节点组成的子树操作是相同的，只需把此子树的左右子节点回链子树根节点即可。
接下来就要考虑向上图这样更高一层的树了。
子树成链表就不用说了，重点是怎么把根节点链到中间去。首先上面根节点开始指针指的是2和6，我们要做的操作是修改指向，让它指3和5.故涉及到链表找节点的问题（这在链表操作很常见，看操作即可）指向完了，回链即可。

代码实现：

/* function TreeNode(x) {this.val = x;this.left = null;this.right = null;
} */
function Convert(pRootOfTree)
{// write code hereif(pRootOfTree==null){return null;}//找左子树最右function find_right(node){while(node.right){node=node.right;}return node;}//拿左子树链表let leftNode = Convert(pRootOfTree.left);//拿右子树右子树let rightNode = Convert(pRootOfTree.right);//链表头节点let  retNode = leftNode;if(leftNode){//若左子树链表存在，则找其最右leftNode = find_right(leftNode);}else{//不存在左子树则根节点就作为链表头节点retNode = pRootOfTree;}//pRootOfTree的左子结点链上leftNodepRootOfTree.left = leftNode;//pRootOfTree的右子结点链上右子结点pRootOfTree.right = rightNode;//回链if(leftNode){leftNode.right = pRootOfTree;}if(rightNode){rightNode.left = pRootOfTree;}//返链表头节点return retNode;}

牛客——二叉搜索树与双向链表-编程部落