专业网站开发平台,个人简历在线制作,响应式网站建设网站,网络营销速成培训班目录
题目#xff1a;剑指 Offer 36. 二叉搜索树与双向链表 - 力扣#xff08;Leetcode#xff09;
题目的接口#xff1a;
解题思路#xff1a;
代码#xff1a;
过啦#xff01;#xff01;#xff01;
写在最后#xff1a; 题目#xff1a;剑指 Offer 36. …目录
题目剑指 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);}
};过啦 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
