文章目錄

• • 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

---

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

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 426. 将二叉搜索树转化为排序的双向链表（BST中序循环遍历）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。