二叉树深度学习——将二叉搜索树转化为排序的双向链表

1.题目解析

题目来源：LCR 155.将二叉搜索树转化为排序的双向链表

测试用例

2.算法原理

首先题目要求原地进行修改并且要求左指针代表前驱指针，右指针代表后继指针，所以思路就是

1.使用前序遍历创建两个指针cur、prev代表当前节点与前一个节点，然后将前一个节点的后继指向当前节点，当前节点的前驱指向上一个节点即可，需要注意的是第一次不能访问前一个节点，因为前一个节点一开始为空，避免对空指针进行操作

2.然后通过创建一个节点head = root，此时root这棵树已经前序遍历完成，使用不断地head =head->left最终访问到root这棵树的最小节点，然后将最小节点的前驱指向最大节点，最大节点的后继指向最小节点，完成循环链表的操作

3.实战代码

/*
// 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:void InOrder(Node* cur,Node*& prev){if(cur == nullptr){return;}InOrder(cur->left,prev);//创建两个指针,不断中序遍历修改指针cur->left = prev;//第一次的prev为空，避免对空指针进行访问if(prev){prev->right = cur;}//更新后继续中序遍历prev = cur;InOrder(cur->right,prev);}Node* treeToDoublyList(Node* root) {if(root == nullptr){return nullptr;}Node* prev = nullptr;InOrder(root,prev);//通过不断向左递归找到最小的节点Node* head = root;while(head->left){head = head->left;}//将最左边的节点的前驱指向最右边节点//最右边节点的后继指向最左边节点head->left = prev;prev->right = head;return head;}
};