本文共 1133 字，大约阅读时间需要 3 分钟。

题目

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

思路

首先思路还是中序遍历完了直接存一vector再弄，但是题目有要求就地完成。

使用一个“上一个”节点来记录，这样的话就可以通过与上一个节点的交互来建立双向链表。

代码

/*// Definition for a Node.class Node {public:    int val;    Node* left;    Node* right;    Node() {}    Node(int _val) {        val = _val;        left = NULL;        right = NULL;    }    Node(int _val, Node* _left, Node* _right) {        val = _val;        left = _left;        right = _right;    }};*/class Solution {public:        Node* treeToDoublyList(Node* root) {        if(root == NULL) return NULL;        Node* head = NULL, *pre = NULL;        inord(root, head, pre);        head->left = pre;        pre->right = head;        return head;    }    void inord(Node* p, Node*& head, Node*& pre) {        if(p == NULL)  return;        inord(p->left, head, pre);        if(head == NULL) {            head = p;   // 找到head            pre = p;    // 对pre进行初始化        } else {            pre->right = p;            p->left = pre;            pre = p;        }        inord(p->right, head, pre);    }    };

转载地址：https://blog.csdn.net/hanmin822/article/details/105716405 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！