当前位置：首页 > news >正文

【LeetCode】剑指 Offer（19）

news 2025/6/22 10:53:21

题目：剑指 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);}
};