面试题36：二叉搜索树和双向链表

文章目录

• • 题目
  • 考点
  • LeetCode版本

题目

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

考点

中序遍历 + 保存前节点 + 保存头节点

LeetCode版本

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