题目描述

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

https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

题解

二叉搜索树的中序遍历是非递减有序的，只需要按照这个顺序把二叉树的各个节点连成双链表即可。

迭代

比较简单的想法是递归进行中序遍历，按顺序存储节点指针，然后再连成双链表。

class Solution {
    vector<Node*> listNodes;
    void dfs(Node* root) {
        if (!root) return;
        dfs(root->left);
        listNodes.push_back(root);
        dfs(root->right);
    }
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        dfs(root);
        Node *pre = nullptr, *head = listNodes[0];
        for (Node* cur : listNodes) {
            if (pre) pre->right = cur;
            cur->left = pre;
            pre = cur;
        }
        head->left = pre;
        pre->right = head;
        return head;
    }
};

时间复杂度 O(N)，空间复杂度 O(N)

递归

我们发现连成链表的操作，也是按照中序遍历的顺序再次遍历实现的，可以尝试将这部分在递归时实现。

class Solution {
    Node *pre = nullptr, *head = nullptr;
    void dfs(Node* cur) {
        if (!cur) return;
        dfs(cur->left);
        if (pre) pre->right = cur;
        else head = cur;
        cur->left = pre;
        pre = cur;
        dfs(cur->right);
    }
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        dfs(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
};