方法一：回溯
解题思路
代码
class Solution {
private:
int mx = INT_MIN, mi = INT_MAX;
Node* start = NULL, * end = NULL;
public:
void Lrotate(Node* root, Node* last_root) { // 针对左子树，左旋
if (!root || !root->right) return ;
Node* temp = root->right;
while (temp->right) temp = temp->right; // 找当前子树的最大值节点
last_root->left = temp;
temp->right = last_root;
}
void Rrotate(Node* root, Node* last_root) { // 针对右子树，右旋
if (!root || !root->left) return ;
Node* temp = root->left;
while (temp->left) temp = temp->left; // 找当前子树的最小值节点
last_root->right = temp;
temp->left = last_root;
}
void dfs(Node* root) { // 回溯，先递归到底层，然后在回溯的过程中转换为双向链表
if (!root) return ;
if (root->val < mi) {
mi = root->val;
start = root;
}
if (root->val > mx) {
mx = root->val;
end = root;
}
dfs(root->left);
dfs(root->right);
Lrotate(root->left, root);
Rrotate(root->right, root);
if (root->left) root->left->right = root;
if (root->right) root->right->left = root;
}
Node* treeToDoublyList(Node* root) {
dfs(root);
if (!start) return NULL;
start->left = end;
end->right = start;
return start;
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间复杂度：\(O(n)\)，递归调用栈空间。
方法二：中序遍历
代码
class Solution {
private:
Node* pre = NULL, * head = NULL; // 通过一个前指针实现转换过程
public:
void dfs(Node* cur) {
if (!cur) return ;
dfs(cur->left);
if (pre != NULL) pre->right = cur;
else head = cur; // 找到最左边节点
cur->left = pre;
pre = cur;
dfs(cur->right);
}
Node* treeToDoublyList(Node* root) {
if (!root) return NULL;
dfs(root);
head->left = pre; // 此时的pre指向最后一个节点
pre->right = head;
return head;
}
};