LeetCode 426. 将二叉搜索树转化为排序的双向链表（BST中序循环遍历）

文章目录

1. 题目2. 解题

1. 题目

将一个 二叉搜索树 就地转化为一个 已排序的双向循环链表 。

对于双向循环列表，你可以将左右孩子指针作为双向循环链表的前驱和后继指针，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

特别地，我们希望可以 就地 完成转换操作。 当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。 还需要返回链表中最小元素的指针。

示例 1：

示例 2： 输入：root = [2,1,3] 输出：[1,2,3] 示例 3： 输入：root = [] 输出：[] 解释：输入是空树，所以输出也是空链表。 示例 4： 输入：root = [1] 输出：[1] 提示： -1000 <= Node.val <= 1000 Node.left.val < Node.val < Node.right.val Node.val 的所有值都是独一无二的 0 <= Number of Nodes <= 2000

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

采用二叉树的非递归遍历写法即可 /* // 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) return root; stack<Node*> stk; Node *cur, *head = NULL, *prev = NULL; while(root || !stk.empty()) { while(root) { stk.push(root); root = root->left; } cur = stk.top(); stk.pop(); if(!head) head = cur;//头结点 root = cur->right; cur->left = prev;//当前节点的前驱 if(prev) prev->right = cur;//前面节点的后驱 prev = cur;//前节点更新 } cur->right = head;//最后的尾节点后继是头 head->left = cur;//头节点的前驱是尾节点 return head;//返回头 } };

12 ms 7.4 MB

---

我的博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！