剑指 Offer 36. 二叉搜索树与双向链表

题目链接：剑指 Offer 36. 二叉搜索树与双向链表

方法一：回溯

解题思路

代码

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;
    }
};