二叉搜索树与双向链表[待加深]

2018/11/4
🍞环境：牛客的编译环境
🍰语言：JavaScript
☕️难点：

• 二叉搜索树的概念：二叉搜索树也叫二叉排序树，规则是所有比根节点小的数都是根节点的左子树中，所有比根节点大的数都是根节点的右子树。
• 开始不太明白将二叉搜索树变成双向链表的意思，根据搜索树的特点，比root节点小的树都在左边，比root节点大的数在右边，转换成双向链表的话，实际上就是指一个数字从小到大排序的双向链表。
  🍊题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向
  🍎思路：
  先找到最左子树，记录该子树，在程序的最后返回该节点。
  找到左子树后，按照二叉搜索树的特点，可以用pre节点去保存左边的节点，之后设置先后即可。
  🍇代码：

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */

function Convert(pRootOfTree)
{
    // write code here
    if(pRootOfTree == null)
        return null;
    var stack = [],
        p = pRootOfTree,
        isFirst = true;
    var pre;
    var root;
    while(p != null || stack.length > 0){
        while(p != null){
            stack.push(p);
            p = p.left;
        }
        p = stack.pop();
        if(isFirst){
            root = p;
            pre = root;
            isFirst = false;
        }else{
            pre.right = p;
            p.left = pre;
            pre = p;
        }
        p = p.right;
    }
    return root;
}