牛客對應題目鏈接：二叉搜索樹與雙向鏈表_牛客題霸_牛客網 (nowcoder.com)

力扣對應題目鏈接：LCR 155. 將二叉搜索樹轉化為排序的雙向鏈表 - 力扣（LeetCode）

---

一、《劍指 Offer》對應內容

---

二、分析題目

上面力扣上的這道題目和牛客上的不太一樣，力扣上的是雙向循環鏈表，而牛客上的并不是循環鏈表，所以返回的是頭結點。

---

三、代碼

//牛客
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:void InOrderConvert(TreeNode* cur, TreeNode*& prev) {if(cur==nullptr) return;InOrderConvert(cur->left, prev);cur->left=prev;if(prev)prev->right=cur;prev=cur;InOrderConvert(cur->right, prev);}TreeNode* Convert(TreeNode* pRootOfTree) {TreeNode* prev=nullptr;InOrderConvert(pRootOfTree, prev);TreeNode* head=pRootOfTree;while(head && head->left)head=head->left;return head;}
};

//力扣
/*
// 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:void InOrderConvert(Node* cur, Node*& prev) {if(cur==nullptr) return;InOrderConvert(cur->left, prev);cur->left=prev;if(prev)prev->right=cur;prev=cur;InOrderConvert(cur->right, prev);}Node* treeToDoublyList(Node* root) {if(root==nullptr) return nullptr;Node* prev=nullptr;InOrderConvert(root, prev);Node* head=root;Node* tail=root;while(head && head->left)head=head->left;while(tail && tail->right)tail=tail->right;head->left=tail;tail->right=head;return head;}
};//另一種寫法
/*
// 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 {
private:Node* prev;Node* head;
public:void dfs(Node* cur){if(cur==NULL) return;dfs(cur->left);if(prev) prev->right=cur;else head=cur;cur->left=prev;prev=cur;dfs(cur->right);}Node* treeToDoublyList(Node* root) {if(root==NULL) return NULL;dfs(root);head->left=prev;prev->right=head;return head;}
};