二叉搜索树与双向链表

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

// 递归版
    function Convert(pRootOfTree) {
      // write code here
      if (pRootOfTree == null) { // 如果根结点为空
        return null;
      }
      if (pRootOfTree.left == null && pRootOfTree.right == null) {
        return pRootOfTree; // 如果只有根结点
      }
      var left = Convert(pRootOfTree.left); // 对左子树递归，left指向左链表的头结点
      var p = left; // 利用辅助结点p来寻找左链表的最后一个结点
      while (p != null && p.right != null) {
        p = p.right;
      }
      if (left != null) { // 如果左链表不为空，将其作为根结点的左子树
        p.right = pRootOfTree;
        pRootOfTree.left = p;
      }
      var right = Convert(pRootOfTree.right); // 对右子树进行递归
      if (right != null) { // 如果右链表不为空，将其拼接到根结点的右结点上
        right.left = pRootOfTree;
        pRootOfTree.right = right;
      }
      return left == null ? pRootOfTree : left; // 返回左链表的头结点或左链表为空时返回根结点
    }

// 非递归版
function Convert(pRootOfTree) {
      var stack = []; // 利用栈对树中的每个结点进行遍历
      var isFirst = true; // 触底反弹的条件
      var p = pRootOfTree; // 操作指针
      var root = null; // 新链表的头结点
      var pre = null; // 操作指针
      if (!pRootOfTree) return null; // 如果树为空
      while (p || stack.length) {
        while (p) {
          stack.push(p);
          p = p.left;
        }
        p = stack.pop();
        if (isFirst) { // 作用是将最左下结点返回给root，即遍历后链表的第一个结点
          root = p;
          pre = root;
          isFirst = false; // isFlag使命完成，只使用一次，后续不再使用
        } else {
          p.left = pre;
          pre.right = p;
          pre = p;
        }
        p = p.right;
      }
      return root;
    }