杭州建设工程信息网站学畅留学招聘网站开发主管

张小明 2026/1/3 10:53:47
杭州建设工程信息网站,学畅留学招聘网站开发主管,网页设计的风格,办网站怎么赚钱目录 基本要求 节点结构 核心算法#xff1a;中序遍历 指针修改 算法思想 递归实现 非递归实现 复杂度分析 时间复杂度#xff1a; 空间复杂度#xff1a; 基本要求 这是一个经典的算法问题#xff1a;将二叉搜索树#xff08;BST#xff09;转换成一个排序的双…目录基本要求节点结构核心算法中序遍历 指针修改算法思想递归实现非递归实现复杂度分析时间复杂度空间复杂度基本要求这是一个经典的算法问题将二叉搜索树BST转换成一个排序的双向循环链表或双向链表。通常题目要求是双向链表中的节点顺序与二叉搜索树的中序遍历顺序一致即升序。需要将节点的左右指针分别作为双向链表的前驱prev和后继next指针。有时要求链表是循环的头尾相连有时只要求是双向链表。原地转换不能创建新节点只能调整原有指针节点结构class Node { public: int val; Node* left; Node* right; Node(int _val) : val(_val), left(nullptr), right(nullptr) {} };核心算法中序遍历 指针修改算法思想利用BST(二叉搜索树)的中序遍历特性中序遍历BST会按升序访问所有节点在遍历过程中记录前一个访问的节点prev将当前节点与prev节点双向连接遍历完成后连接头尾节点形成循环递归实现class Solution { private: Node* prev nullptr; // 记录前驱节点 Node* head nullptr; // 记录链表头节点 // 中序遍历递归函数 void inorderTraversal(Node* curr) { if (!curr) return; // 1. 递归遍历左子树 inorderTraversal(curr-left); // 2. 处理当前节点 if (!prev) { // 第一个节点最小值设为头节点 head curr; } else { // 连接前驱和当前节点 prev-right curr; curr-left prev; } // 更新prev为当前节点 prev curr; // 3. 递归遍历右子树 inorderTraversal(curr-right); } public: Node* treeToDoublyList(Node* root) { if (!root) return nullptr; // 中序遍历并调整指针 inorderTraversal(root); //如果需要转换BST为双向循环链表不需要删除下面两行代码即可 // 连接头尾形成循环链表 head-left prev; // 头的前驱指向尾 prev-right head; // 尾的后继指向头 return head; } };非递归实现不使用递归通过显式栈来模拟中序遍历的过程在遍历过程中调整指针指向。class Solution { public: Node* treeToDoublyList(Node* root) { if (!root) return nullptr; Node* prev nullptr; Node* head nullptr; stackNode* st; Node* curr root; // 中序遍历迭代版 while (curr || !st.empty()) { // 左子树入栈 while (curr) { st.push(curr); curr curr-left; } // 弹出当前节点 curr st.top(); st.pop(); // 连接节点 if (!prev) { head curr; // 第一个节点 } else { prev-right curr; curr-left prev; } prev curr; curr curr-right; // 处理右子树 } //如果需要转换BST为双向循环链表不需要删除下面两行代码即可 // 形成循环 head-left prev; prev-right head; return head; } };复杂度分析时间复杂度O(n)每个节点被访问一次n为节点总数空间复杂度O(h)h为树的高度最坏情况链状树O(n)最好情况平衡树O(log n)
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:809451989@qq.com进行投诉反馈,一经查实,立即删除!

seo推广软件aso优化违法吗

开源贡献终极指南:从新手到专家的快速成长路径 【免费下载链接】vcr Record your test suites HTTP interactions and replay them during future test runs for fast, deterministic, accurate tests. 项目地址: https://gitcode.com/gh_mirrors/vc/vcr 你是…

张小明 2026/1/3 3:22:07 网站建设

广东网站se0优化公司重庆网站搭建

Markdown转PPT革命性工具:内容创作效率的颠覆性提升 【免费下载链接】md2pptx Markdown To PowerPoint converter 项目地址: https://gitcode.com/gh_mirrors/md/md2pptx 在数字化工作场景中,演示文稿制作已成为技术文档编写者、培训讲师和项目汇…

张小明 2026/1/3 3:22:04 网站建设

邢台做网站的公司哪家好?wordpress最好用的采集插件

四轮轮毂电机驱动车辆电机附加能量损耗、电机能量总损耗、轮胎滑移能量与车辆稳定性之间的协调优化控制、仿真搭建整体采用分层控制策略。 其中顶层控制器的任务是利用车辆状态信息、横摆角速度以及质心侧偏角的误差计算出维持车辆稳定性的期望附加横摆力矩。 为了减少车辆速度…

张小明 2026/1/3 3:22:01 网站建设

做网站选择什么相机织梦后台发布了网站没显示

res-downloader是一款基于网络请求拦截技术的专业资源下载工具,通过智能嗅探和解析机制,实现视频、图片、音频等网络资源的自动化捕获与下载。该工具支持微信视频号、抖音、快手等主流平台的资源下载,为用户提供高效的无水印内容保存方案。 【…

张小明 2025/12/31 6:14:14 网站建设

咸阳企业网站设计开发制作湖北网站

2025新范式:零基础构建专业AI Agent——v0s与Latitude集成实战指南 【免费下载链接】v0-system-prompts-models-and-tools 项目地址: https://gitcode.com/GitHub_Trending/v0s/v0-system-prompts-models-and-tools 你还在为构建AI Agent时的复杂配置而头疼…

张小明 2026/1/1 19:14:54 网站建设

快速搭建网站的好处WordPress的MySQL搭建

STL deque 的详细特征 基本特性 #include <deque> using namespace std;deque<int> dq; // 声明一个int类型的双端队列 双端队列&#xff1a;允许在两端进行高效插入和删除动态数组&#xff1a;支持随机访问&#xff0c;可以像数组一样通过下标访问内存结构&a…

张小明 2026/1/2 7:07:06 网站建设