每日一题：LeetCode-LCR 155. 将二叉搜索树转化为排序的双向链表

作者：半亩房顶

2024-01-31
北京
本文字数：1004 字
阅读完需：约 3 分钟

刷题使我快乐，满脸开心.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);    }};