二叉搜索树与双向链表 2022-03-01 周一

题目

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

学习

• 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。

• 双向链表： 在构建相邻节点的引用关系时，设前驱节点 pre 和当前节点 cur ，不仅应构建 pre.right = cur ，也应构建 cur.left = pre 。

• 循环链表： 设链表头节点 head 和尾节点 tail ，则应构建 head.left = tail 和 tail.right = head 。

参考1

参考2

思路

• 二叉搜索树的中序遍历为 递增序列 。 ===>实现了问题的转化

• 二叉搜索树和双向链表的对比。
  左子树(left)===前驱(previous)
  右子树(right)===当前(current)（或者后继next）（到底选哪个语义看情况）

• 循环链表：head和tail
  head的前驱是tail: head.left = tail; (head.previous = tail)
  tail的后继是head: tail.right = head; (tail.next = head)

JS代码

/**
 * // Definition for a Node.
 * function Node(val,left,right) {
 *    this.val = val;
 *    this.left = left;
 *    this.right = right;
 * };
 */
/**
 * @param {Node} root
 * @return {Node}
 */
var treeToDoublyList = function(root) {
    // 判空
    if (!root) {
        return null;
    }

    // 定义中序遍历内部方法
    let head = null;
    let previous = null; // 移动到最后，就是tail

    const inOrder = (current) => {
        if (!current) {
            return;
        }

        // 中序遍历，先递归左子树
        inOrder(current.left);

        // 设置前驱节点
        // 如果前置指针空了，那么是头结点
        if (!previous) {
            head = current;
        } else {
            previous.right = current;
            current.left = previous;
        }
        
        // 移动前置节点到当前，然后继续遍历右子树去了
        previous = current;

        // 遍历右子树
        inOrder(current.right);
    }

    // 执行中序遍历
    inOrder(root);

    // 甚至循环链表
    // 中序遍历之后，previous就是尾结点tail
    head.left = previous;
    previous.right = head;

    // 返回头节点
    return head;
};

备注

中序遍历作为内部函数，有点不好理解。