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

杭州建设工程信息网站,学畅留学招聘网站开发主管,网页设计的风格,办网站怎么赚钱目录 基本要求 节点结构 核心算法#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)