[剑指-Offer] 36. 二叉搜索树与双向链表(中序遍历、递归)

1. 题目来源

链接： 二叉搜索树与双向链表
来源：LeetCode——《剑指-Offer》专项

2. 题目说明

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

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

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

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

注意：

• 此题对比原题有改动。

3. 题目解析

方法一：中序遍历+递归解法

跟 BST 有关的题，肯定要利用其性质，即 左<根<右。而且十有八九都得用 中序遍历 来解，中序遍历的顺序就是左根右，得到有序序列，跟性质完美吻合。观察到原二叉搜索树中结点 4 连接着结点 2 和结点 5，而在双向链表中，连接的是结点 3 和结点 5，这就是为啥要用中序遍历了，因为只有中序遍历，结点 3 之后才会遍历到结点 4，这时候可以将结点 3 和结点 4 串起来。

树的问题大多离不开递归，一定要熟练掌握。返回的结点不再是原二叉搜索树的根结点 root 了，而是最左结点，即最小值结点。

再写中序遍历之前，还有一个难点：需要把相邻的结点连接起来，所以需要知道上一个遍历到的结点是什么，需要用一个变量 pre，来记录上一个遍历到的结点。还需要一个变量 head，来记录最左结点，也就是双向链表的头结点。

这样的话，在递归函数中，先判空，之后对左子结点调用递归，这样会先一直递归到最左结点，此时如果 head 为空的话，说明当前就是最左结点，赋值给 head 和 pre，对于之后的遍历到的结点，那么可以和 pre 相互连接上，然后 pre 赋值为当前结点 node，再对右子结点调用递归即可。主要连接的语句有以下三条：

 	pre->right = node;
    node->left = pre;
    pre = node;

我觉得《剑指-Offer》没讲太清楚，在这在强调一下，理解这个一定要理解中序遍历：

• 中序遍历至右节点后说明根包括其左子树已经全部遍历完毕，即已经转化为双向链表
• pre->right = node，pre 就是上一个遍历的节点，它永远指向比自己大的节点，此时 pre 已经被遍历过了，操作 pre 不会影响中序遍历的结果
• node->left = pre，它永远指向比自己小的节点，
• 还有就是树/子树的根节点与其左子树的最右节点（前驱节点）之间的联系，也可以通过三段代码直接完成

建议画图，理解…确实很抽象。

参见代码如下：

// 执行用时 :8 ms, 在所有 C++ 提交中击败了84.14%的用户
// 内存消耗 :10 MB, 在所有 C++ 提交中击败了100.00%的用户

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (root == nullptr) return nullptr;
        Node *head = nullptr, *pre = nullptr;
        inorder(root, pre, head);
        pre->right = head;
        head->left = pre;
        return head;
    }
    void inorder(Node* node, Node*& pre, Node*& head) {
        if (node == nullptr) return;
        inorder(node->left, pre, head);
        if (head == nullptr) {
            head = node;
            pre = node;
        } else {
            pre->right = node;
            node->left = pre;
            pre = node;
        }
        inorder(node->right, pre, head);
    }
};