題目描述：輸入一棵二叉搜索樹(shù)，將該二叉搜索樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只能調(diào)整樹(shù)中結(jié)點(diǎn)指針的指向。

// 遞歸版
    function Convert(pRootOfTree) {
      // write code here
      if (pRootOfTree == null) { // 如果根結(jié)點(diǎn)為空
        return null;
      }
      if (pRootOfTree.left == null && pRootOfTree.right == null) {
        return pRootOfTree; // 如果只有根結(jié)點(diǎn)
      }
      var left = Convert(pRootOfTree.left); // 對(duì)左子樹(shù)遞歸，left指向左鏈表的頭結(jié)點(diǎn)
      var p = left; // 利用輔助結(jié)點(diǎn)p來(lái)尋找左鏈表的最后一個(gè)結(jié)點(diǎn)
      while (p != null && p.right != null) {
        p = p.right;
      }
      if (left != null) { // 如果左鏈表不為空，將其作為根結(jié)點(diǎn)的左子樹(shù)
        p.right = pRootOfTree;
        pRootOfTree.left = p;
      }
      var right = Convert(pRootOfTree.right); // 對(duì)右子樹(shù)進(jìn)行遞歸
      if (right != null) { // 如果右鏈表不為空，將其拼接到根結(jié)點(diǎn)的右結(jié)點(diǎn)上
        right.left = pRootOfTree;
        pRootOfTree.right = right;
      }
      return left == null ? pRootOfTree : left; // 返回左鏈表的頭結(jié)點(diǎn)或左鏈表為空時(shí)返回根結(jié)點(diǎn)
    }

// 非遞歸版
function Convert(pRootOfTree) {
      var stack = []; // 利用棧對(duì)樹(shù)中的每個(gè)結(jié)點(diǎn)進(jìn)行遍歷
      var isFirst = true; // 觸底反彈的條件
      var p = pRootOfTree; // 操作指針
      var root = null; // 新鏈表的頭結(jié)點(diǎn)
      var pre = null; // 操作指針
      if (!pRootOfTree) return null; // 如果樹(shù)為空
      while (p || stack.length) {
        while (p) {
          stack.push(p);
          p = p.left;
        }
        p = stack.pop();
        if (isFirst) { // 作用是將最左下結(jié)點(diǎn)返回給root，即遍歷后鏈表的第一個(gè)結(jié)點(diǎn)
          root = p;
          pre = root;
          isFirst = false; // isFlag使命完成，只使用一次，后續(xù)不再使用
        } else {
          p.left = pre;
          pre.right = p;
          pre = p;
        }
        p = p.right;
      }
      return root;
    }