剑指 Offer 36. 二叉搜索树与双向链表

题目

题目来源：力扣（LeetCode）

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

为了让您更好地理解问题，以下面的二叉搜索树为例：

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

思路分析

二叉搜索树
二叉搜索树（Binary Search Tree），也称为 二叉查找树、有序二叉树或排序二叉树，是指一棵空树或者具有下列性质的二叉树：

1. 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不为空，则右子树上所有子节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉搜索树；

二叉搜索树的中序遍历的遍历顺序为： 左子树 -> 根节点 -> 右子树，二叉搜索树的中序遍历的结果是一个递增的序列。

中序遍历递归模板

inOrder(node) {
  // 遍历顺序：左子树 -> 根节点 -> 右子树
  if (node != null) {
    // 递归边左子树
    inOrder(node.left);
    // 打印根节点
    console.log(node.val);
    // 递归遍历右子树
    inOrder(node.right);
  }
}

题意要求我们将 二叉搜索树 转换成一个 “排序的循环双向链表”，其中包含三个要素：

1. 排序链表：节点应从小到大排序，中序遍历的结果是递增序列，因此应使用中序遍历从小到大访问树的节点
2. 双向链表：在构建相邻节点的引用关系时，设前驱节点 pre 和当前节点 cur，设置前驱节点 pre 的后继指针指向 cur 节点，cur 节点的的后继指针指向前驱节点 pre，即应构建pre.right = cur和cur.left = pre。
3. 循环链表：设链表头节点为 head，尾节点为 tail，设置头节点 head 的后继指针指向尾节点 tail，也要设置尾节点 tail 的前驱指针指向头节点head，即应构建head.left = tail和tail.right = head。

如下图：(借用官方的图)

算法流程

1. 终止条件： 当节点 cur 为空，代表越过叶节点，直接返回；
2. 递归左子树，即 dfs(cur.left) ；
3. 构建链表：
   1. 当 pre 为空时： 代表正在访问链表头节点，记为 head ；
   2. 当 pre 不为空时： 修改双向节点引用，即 pre.right = cur ， cur.left = pre ；
   3. 保存 cur ： 更新 pre = cur ，即节点 cur 是后继节点的 pre ；
4. 递归右子树，即 dfs(cur.right)

具体过程
1、我们定义两个指针 pre 和 head，pre 指针用于保存中序遍历的前一个节点，head 指针用于记录排序链表的头节点。

2、中序遍历二叉树，因为是中序遍历，所以遍历顺序就是双线链表的建立顺序。我们只需要在中序遍历的过程中，修改每个节点的左右指针，将零散的节点连接成双向循环链表。

3、首先遍历二叉树的左子树，然后是当前根节点root。

• 当前驱节点pre不为空时，将前驱节点pre的左指针指向当前根节点root，即pre.right = root。

• 当前驱节点pre为空时： 代表正在访问链表头节点，记为 head = root ，保存头节点。

4、每一个root节点访问时它的左子树肯定被访问过了，因此放心修改它的left指针，将root的left指针指向它的前驱节点，即 root.left = pre， 这样两个节点之间的双向指针就修改好了。

5、然后前驱节点pre右移到当前root节点，接下来递归到右子树重复上述操作。

6、完成以上各步，只是将二叉树变成了双向排序链表，我们还需要将链表的首尾连接到一起，将其变成双向循环排序链表。

head.left = pre;
pre.right = head;

代码

/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var in_order = function (root) {
  if (root == null) return;
  // 搭建中序遍历的过程
  in_order(root.left);
  // 在中序遍历的过程中做操作
  if (pre == null) {
    // 前驱节点为空，代表正在访问链表头节点，将 head 指向 root，保存头节点
    head = root;
  } else {
    // 前驱节点 pre 不为空，前驱节点 pre 的right 指针指向 root
    pre.right = root;
  }
  // 修改 root 节点的 left 指针，将 left 指针指向它的前驱节点
  root.left = pre;
  // 前驱节点 pre 右移到当前 root 节点
  pre = root;
  // 遍历右子树
  in_order(root.right);
  return;
}
var treeToDoublyList = function (root) {
  if (root == null) return null;
  head = pre = null;
  // 中序遍历，得到一条链表，head是链表的头，pre是链表的尾部，
  in_order(root);
  // 把链表连接起来，变成循环双端链表
  head.left = pre;
  pre.right = head;
  return head;
};