426. Convert Binary Search Tree to Sorted Doubly Linked List

🟠   🔖  栈 树 深度优先搜索 二叉搜索树 链表 二叉树 双向链表  🔗 LeetCode

题目

Convert a BST to a sorted circular doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

Let's take the following BST as an example, it may help you understand the problem better:

We want to transform this BST into a circular doubly linked list. Each node in a doubly linked list has a predecessor and successor. For a circular doubly linked list, the predecessor of the head element is the tail element, and the successor of the tail element is the head element.

The figure below shows the circular doubly linked list for the BST above. The "head" symbol means the node it points to is the smallest element of the linked list.

Specifically, we want to do the transformation in place. After the transformation, the left pointer of the tree node should point to its predecessor, and the right pointer should point to its successor. We should return the pointer to the head element of the linked list.

The figure below shows the transformed BST. The solid line indicates the successor relationship, while the dashed line means the predecessor relationship.

题目大意

将一个二叉搜索树就地转化为一个已排序的双向循环链表。可以将左右孩子指针作为双向循环链表的前驱和后继指针。

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

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

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

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

下图显示了转化后的二叉搜索树，实线表示后继关系，虚线表示前驱关系。

解题思路

二叉搜索树的中序遍历结果是有序的，因此要将一个二叉搜索树就地转化为一个已排序的双向循环链表，可以采用中序遍历的方式，将节点的左右指针分别指向前驱和后继节点。最后，调整头尾节点的前驱和后继指针，形成循环链表。

1. 定义两个指针 head 和 tail，它们分别表示双向链表的头部和尾部。
2. 定义一个中序遍历的函数 traverse，其中对每个节点进行如下处理：
   • 如果 head 为空，将当前节点赋值给 head。
   • 如果 tail 不为空，将 tail 的右指针指向当前节点，将当前节点的左指针指向 tail。
   • 更新 tail 为当前节点。
3. 在 traverse 完成中序遍历后，将 head 和 tail 进行连接，形成双向循环链表。
   • 将 head 的左指针指向 tail。
   • 将 tail 的右指针指向 head。

这样，我们就完成了将 BST 转化为已排序的双向循环链表。最后，返回 head 作为循环链表的头节点。

这个解决方案的时间复杂度是 O(n)，其中 n 是二叉搜索树的节点数量。因为我们需要访问每个节点一次，完成中序遍历。空间复杂度是 O(h)，其中 h 是二叉搜索树的高度，表示递归调用栈的深度。

代码

/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function (root) {
  if (!root) return null;
  let head = null;
  let tail = null;

  const traverse = (root) => {
    if (!root) return null;
    traverse(root.left);

    // 处理当前节点
    if (!head) {
      head = root;
    }
    if (tail) {
      tail.right = root;
      root.left = tail;
    }
    tail = root;

    traverse(root.right);
  };

  // 开始中序遍历
  traverse(root);

  // 将头尾相连形成循环链表
  head.left = tail;
  tail.right = head;
  return head;
};