剑指offer（26）二叉搜索树与双向链表

题目描述

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

题目分析

要生成排序的双向列表，那么只能是中序遍历，因为中序遍历才能从小到大，所以需要递归，

• 先对左子数调整为双向链表，并用变量pLast指向最后一个节点
• 再将中间节点和pLast连起来
• 再去调整右子树

代码

/* function TreeNode(x) {

 this.val = x;

 this.left = null;

 this.right = null;

 } */

function Convert(pRootOfTree) {

  // write code here

  if (pRootOfTree === null) return null;

  let pLast = null;

  pLast = ConvertNode(pRootOfTree, pLast);

  let pHead = pLast;

  while (pHead && pHead.left) {

    pHead = pHead.left;

  }

  return pHead;

}

function ConvertNode(pNode, pLast) {

  if (pNode === null) return;

  if (pNode.left) {

    pLast = ConvertNode(pNode.left, pLast);

  }

  pNode.left = pLast;

  if (pLast) {

    pLast.right = pNode;

  }

  pLast = pNode;

  if (pNode.right) {

    pLast = ConvertNode(pNode.right, pLast);

  }

  return pLast;

}