转为排序的双向链表

为什么中序遍历就能转成有序双向链表？

• 依据: 二叉搜索树的中序序列就是升序;
• 做法: 按中序访问顺序把相邻节点两两相连, 复用 left 作为前驱指针、right 作为后继指针;

中序加尾指针如何实现？

• 维护两个变量: head 记录第一个访问的节点, tail 记录上一个访问的节点;
• 处理当前节点: tail 非空时与它互相连接, 否则当前节点就是 head; 处理完把 tail 移到当前节点;
• 收尾: 让 head 与 tail 互连形成循环双向链表;

const treeToDoublyList = function (root) {
  if (root == null) return null;
  let head = null;
  let tail = null;
  const dfs = (node) => {
    if (node == null) return;
    dfs(node.left);
    if (tail == null) head = node;
    else {
      tail.right = node;
      node.left = tail;
    }
    tail = node;
    dfs(node.right);
  };

  dfs(root);
  head.left = tail;
  tail.right = head;
  return head;
};

复杂度如何？

• 时间: O(n), 每个节点访问一次;
• 空间: O(n) 递归栈, 不计返回的链表本身;