36.二叉搜索树与双向链表 (Medium)*

题目描述*

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

代码*

二叉搜索树中序遍历就是有序序列，直接修改中序遍历的递归代码即可。保存 head 和 tail 指针在遍历后连接头尾。

递归迭代

class Solution {
private:
    Node *head = nullptr;
    Node *tail = nullptr;
    void helper(Node *root) {
        if(root == nullptr) {
            return;
        }
        helper(root->left);
        if(tail == nullptr) {
            head = root;
        }else {
            tail->right = root;
        }
        root->left = tail;
        tail = root;
        helper(root->right);
    }
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) {
            return nullptr;
        }
        helper(root);
        head->left = tail;
        tail->right = head;
        return head;
    }
};

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(root == nullptr) {
            return nullptr;
        }
        stack<Node*> st;
        auto cur = root;
        Node* head = nullptr;
        Node* tail = nullptr;
        while(cur != nullptr || !st.empty()) {
            while(cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top();
            st.pop();
            if(tail == nullptr) {
                head = cur;
            }else {
                tail->right = cur;
            }
            cur->left = tail;
            tail = cur;
            cur = cur->right;
        } 
        tail->right = head;
        head->left = tail;
        return head;
    }
};

最后更新: July 23, 2022