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

大家好,我是吴师兄。

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

# 一、题目描述

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

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

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

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

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

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

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

# 二、题目解析

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

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

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

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

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

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

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

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

具体操作如下:

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

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

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

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

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

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

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

8、这样,precur 两个节点的双向指针都设置好了,接下来让前驱节点 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);
    }
}