牛客——二叉搜索树与双向链表

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

题目分析
这道题怎么说呢，牛客标它的难度是最低的这我是不太认同的。首先从题目描述来看，不读个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 here
    if(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的左子结点链上leftNode
        pRootOfTree.left = leftNode;
        //pRootOfTree的右子结点链上右子结点
        pRootOfTree.right = rightNode;
        //回链
        if(leftNode){
             leftNode.right = pRootOfTree;
        }
        if(rightNode){
           rightNode.left = pRootOfTree;
        }
        //返链表头节点
        return retNode;
    
    
}