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

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

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

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

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

对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以就地完成转换操作。

当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。

还需要返回链表中的第一个节点的指针。

二、题目解析

这道题目首先得掌握以下基础概念：

• 1、二叉搜索树
• 2、中序遍历的递归写法

二叉搜索树是一棵有序的二叉树，它具有如下的性质：

• 1、若它的左子树不为空，那么左子树上的所有值均小于它的根节点
• 2、若它的右子树不为空，那么右子树上所有值均大于它的根节点
• 3、它的左子树和右子树也都是二叉搜索树

而中序遍历的递归过程是 左 ---》根 ---》右 的顺序。

所以，如果对二叉搜索树采取中序遍历的方式，那么得到的序列是一个从小到大排列的序列。

而在题目中，最终得到的双向链表正是这种顺序。

因此，我们采取中序遍历的操作来将二叉搜索树变成排序的循环双向链表。

具体操作如下：

1、定义两个指针 pre 和 head ，pre 表示中序遍历过程中访问当前节点时的前一个节点，head 表示双向链表的头节点。

2、开始中序遍历二叉树，用 cur 表示当前正在访问的那个节点，由于中序遍历的递归过程是 左 ---》根 ---》右 的顺序，因此会先遍历二叉树的左子树。

3、由于 pre 表示中序遍历过程中访问当前节点 cur 时的前一个节点，因此 pre 是 cur 的前驱节点，相应的 cur 是 pre 的后继节点。

4、根据题目要求，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。

5、所以，如果 pre 不为空，可以直接将 pre 的右指针指向后继节点 cur，即 pre->right = cur。

6、而如果 pre 为空，那么说明 cur 是访问的第一个节点，即是双向链表的头节点，那么需要设置 head = cur。

7、由于中序遍历的递归过程是 左 ---》根 ---》右 的顺序，因此处理当前节点 cur 时，它的左子树必然已经遍历操作过，前驱节点 pre 就在它的左子树中，因此设置 cur->left = pre。

8、这样，pre 和 cur 两个节点的双向指针都设置好了，接下来让前驱节点 pre 移动到当前 cur 节点的位置。

9、由于中序遍历的递归过程是 左 ---》根 ---》右 的顺序，因此在递归的遍历当前节点 cur 的右子树。

10、经过中序遍历之后，除了头节点和尾节点，每个节点都已经设置好了双向指针。

11、最后将链表的头节点和尾节点相连就完成了双向循环链表的转换。

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 剑指 Offer 36. 二叉搜索树与双向链表：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/ 
class Solution {

    // pre 表示当前访问节点的前驱节点，并且每次都会跟随当前节点向后移动
    // 此时，由于当前访问节点为空，所以 pre 也默认为空
    Node pre = null ;

    // head 表示指向链表中有最小元素的节点
    // 此时，由于当前访问节点为空，所以 head 也默认为空
    Node head = null;

    public Node treeToDoublyList(Node root) {

        // 边界处理，如果当前节点为空，直接返回空
        if(root == null) return null;

        // 否则递归的采取中序遍历的方式遍历二叉搜索树
        dfs(root);

        // 经过中序遍历后，二叉搜索树已经安装从小到大的顺序进行了排序

        // head 表示指向链表中有最小元素的节点
        // pre 表示当前访问节点的前驱节点，并且每次都会跟随当前节点向后移动
        // 跳出 dfs 时，当前节点为 null，pre 指向了排序之后的最后一个节点

        // 1、由于对于双向循环链表，第一个节点的前驱是最后一个节点
        // 2、树中节点的左指针需要指向前驱
        // 因此 head.left = pre
        head.left = pre;

        // 1、由于对于双向循环链表，最后一个节点的后继是第一个节点
        // 2、树中节点的右指针需要指向后继
        // 因此 pre.right = head
        pre.right = head;

        // 最后，返回链表中的第一个节点的指针即可
        return head;
    }

    void dfs(Node cur) {
        
        // 递归终止条件，即越过了叶子节点
        if(cur == null) return;

        // 中序遍历的递归过程顺序是：左、根、右

        // 先递归的处理左子树
        dfs(cur.left);

        // 在访问当前节点 cur ，即【根】节点的过程中开始构建双向链表

        // pre 表示当前访问节点的前驱节点，并且每次都会跟随当前节点向后移动
        // 同时也意味着 cur 是 pre 的后继节点
        // 如果 pre 不为空，说明双向链表上已经有节点了
        if(pre != null){

            // 树中节点的右指针需要指向后继
            // pre.right = cur
            pre.right = cur;

        // 如果 pre 为空，说明双向链表上还没有节点
        }else{
             
             // head 表示指向链表中有最小元素的节点
             // 此时，cur 就是最先访问的节点，即中序遍历过程中最小的元素
             head = cur;

        }

        // 树中节点的左指针需要指向前驱
        cur.left = pre;

        // 此时，cur 这个节点的左指针已经设置完毕
        // pre 来到 cur 这个节点的位置
        pre = cur;

        // 最后再递归的处理右子树
        dfs(cur.right);
    }
}