在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
原创博文,转载请注明出处! # 题目输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。
struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }
# 思路
# 代码class Solution { public: TreeNode* Convert(TreeNode* pRootOfTree) { if(pRootOfTree == nullptr) return nullptr; // 双向链表尾节点 TreeNode* list_last = nullptr; // 递归建立双向链表 ConvertNode(pRootOfTree,list_last); // 查找双向链表首节点 while(list_last->left != nullptr) { list_last = list_last->left; } // 返回双向链表的首节点 return list_last; } // 对BST中序遍历,得到有序序列;调整序列元素的指针,将有序序列调整为双向链表 void ConvertNode(TreeNode* cur,TreeNode *&list_last) // 注意形参 { // 边界条件(递归出口) if(cur==nullptr) return ; // 遍历左子树 if(cur->left != nullptr) ConvertNode(cur->left,list_last); // 建立双向链接 cur->left = list_last; // 单侧链接 if(list_last != nullptr) list_last->right = cur; // 单侧链接 list_last = cur; //遍历右子树 if(cur->right != nullptr) ConvertNode(cur->right,list_last); } };
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论