本文共 906 字，大约阅读时间需要 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 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！