将BST转成有序的双向链表，left指向前一个元素，right指向后面。BST中序遍历得到的是从小到大有序列表。因此维持一个global pre，做中序遍历时把cur->left改成pre, 并更新Pre。最后再把首尾结点串起来。
class Solution {
public:
Node *pre;
Node* treeToDoublyList(Node* root) {
if (root == nullptr) return nullptr;
Node *header = new Node(-1);
pre = header;
inorder(root);
header->right->left = pre;
pre->right = header->right;
return header->right;
}
void inorder(Node *cur) {
if (cur == nullptr) return;
inorder(cur->left);
pre->right = cur;
cur->left = pre;
pre = cur;
inorder(cur->right);
}
};
/**
* Definition of TreeNode:
* class TreeNode {
* public:
* int val;
* TreeNode *left, *right;
* TreeNode(int val) {
* this->val = val;
* this->left = this->right = NULL;
* }
* }
*/
class Solution {
public:
/**
* @param root: root of a tree
* @return: head
* node of a doubly linked list
*/
TreeNode *first = nullptr, *cur = nullptr;
void inorder(TreeNode *node) {
if (node == nullptr) return;
inorder(node->left);
if (cur == nullptr) first = node;
else cur->right = node;
node->left = cur;
cur = node;
inorder(node->right);
}
TreeNode * treeToDoublyList(TreeNode * root) {
if (root == nullptr) return nullptr;
inorder(root);
first->left = cur;
cur->right = first;
return first;
}
};