刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

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

示例 1：

输入：root = [4,2,5,1,3] 

输出：[1,2,3,4,5]

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

示例 2：

输入：root = [2,1,3]
输出：[1,2,3]

示例 3：

输入：root = []
输出：[]
解释：输入是空树，所以输出也是空链表。

示例 4：

输入：root = [1]
输出：[1]

提示：

• -1000 <= Node.val <= 1000
• Node.left.val < Node.val < Node.right.val
• Node.val 的所有值都是独一无二的
• 0 <= Number of Nodes <= 2000

思路

这个题目还是挺有意思的，关键点有几个

• 二叉搜索树的概念及其遍历方式
• 因需要原地生成，所以在生成排序链表的同时，要不影响后续节点的加入

第二点往往会被忽略，因为选择了dfs的话，下意识从最深处节点开始（也就是排序后的最小值）一个个链接，此时正好符合了第二点的要求。

二叉搜索树特点：

• 左子树所有节点均小于根节点
• 右子树所有节点均大于根节点

所以在此情况下解法就出来了：

• DFS前序遍历，遍历节点
• 使用头尾双指针方法，将一个个节点拼接起来，最终再拼接头尾即可

至此，上代码

代码

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) return nullptr;
        dfs(root);
        // 拼接头尾
        head->left = tail;
        tail->right = head;
        return head;
    }
private:
    Node *tail, *head;
    void dfs(Node* now) {
        if(now == nullptr) return;
        dfs(now->left);
        // 开始时确定头结点，使用尾结点作为缓存指针拼接后续节点
        if(tail != nullptr) tail->right = now;
        else head = now;
        now->left = tail;
        // 移动尾部指针，等待拼接下一个
        tail = now;
        dfs(now->right);
    }
};