目录

题目：剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

题目：剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（Leetcode）

题目的接口：

/*// 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) {    }};

解题思路：

这道题，我的想法就是：

中序遍历这一棵二叉搜索树，

然后让他的头指向尾，尾指向头，

递归让每个节点都做一遍，就形成双向链表。

首先中序遍历找到第一个节点cur：

 更新头节点，然后让他指向尾节点，

等找到尾节点时，让尾节点再指向头节点：

 然后继续找下一个头节点与尾节点互指：

 以此类推，

直到中序遍历完整棵二叉搜索树，

最后，再将最开始的头节点head指向最后的尾节点，

最后的尾节点再指向head，

再返回双向链表的头head即可。

代码：

/*// 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;        }        //中序遍历        dfs(root);        //头节点指向尾        head->left = pre;        //尾节点指向头        pre->right = head;        return head;    }private:    //创建头尾节点指针    Node* head, *pre;    //中序遍历实现    void dfs(Node* cur)    {        //遍历到底了，返回上一级        if(cur == nullptr)        {            return;        }        //递归左子树        dfs(cur->left);        //之后每一次到这里，让尾节点指向头节点        if(pre != nullptr)        {            pre->right = cur;        }        else//第一次到这里的时候，让头指针指向cur(中序遍历第一个节点)        {            head = cur;        }        //让头节点指向尾节点        cur->left = pre;        //更新尾节点        pre = cur;        //递归右子树        dfs(cur->right);    }};

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果喜欢本文的话，欢迎点赞和评论，写下你的见解。

如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。

之后我还会输出更多高质量内容，欢迎收看。