将二叉搜索树转化为排序的双向链表

链接：

​​​​​​LCR 155. 将二叉搜索树转化为排序的双向链表

题解：

/*
// 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) {_head = _tail = nullptr;dfs(root);if (_tail) {_tail->right = _head;_head->left = _tail;}return _head;}
private:void dfs(Node* root) {if (!root) {return;}dfs(root->left);if (_head == nullptr) {_head = root;_tail = root;} else {_tail->right = root;root->left = _tail;_tail = root;}dfs(root->right);}
private:Node* _head;Node* _tail;
};