二叉搜索树与双向链表.md

题目

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

思路

二叉搜索树的中序遍历即排序后的序列

• 1.递归左子树，找到左子树的最后一个节点，根节点左侧连接到左子树的最后一个节点
• 2.当前节点变为已经转换完成的链表的最后一个节点
• 3.递归右子树，找到当前树的最后一个节点
• 4.回溯到上一层，进行链接...

代码

    function Convert(pRootOfTree) {
      if (!pRootOfTree) {
        return null;
      }
      ConvertCore(pRootOfTree);
      while (pRootOfTree.left) {
        pRootOfTree = pRootOfTree.left;
      }
      return pRootOfTree;
    }

    function ConvertCore(node, last) {
      if (node.left) {
        last = ConvertCore(node.left, last)
      }
      node.left = last;
      if (last) {
        last.right = node;
      }
      last = node;
      if (node.right) {
        last = ConvertCore(node.right, last);
      }
      return last;
    }

考察点

• 二叉搜索树
• 链表