二叉搜索树与双向链表
题目描述
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
注意：本题与主站 426 题相同：https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/
注意：此题对比原题有改动。
解法：
对二叉树搜索树做中序遍历，得到的序列就是递增的。仅需要在遍历的过程中，把每个节点和前一个节点连起来。
先找出最终链表的头结点，头节点为最终的返回值。因为遍历的过程中会修改二叉树，因此该步骤要提前进行。
在遍历的过程中，使用前驱节点的 right 指向当前节点，当前节点的 left 指向前驱节点，然后更新前驱节点。
遍历完成后，得到了一个双向链表，此时再把 head 和 tail 连起来，就构成了循环链表。
class Solution {
public:
Node* treeToDoublyList(Node* root) {
if(!root) return nullptr;
Node *head = root;
while(head->left){
head = head->left;
}
Node *pre = nullptr;
traversal(root, &pre);
Node* tail = pre;
tail->right = head;
head->left = tail;
return head;
}
void traversal(Node* node, Node** pre){
if(node == nullptr) return;
traversal(node->left, pre);
if(*pre != nullptr){
(*pre)->right = node;
}
node->left = *pre;
*pre = node;
traversal(node->right, pre);
}
};
有一种想法是，一开始就找到 tail，然后把初始的前驱节点设置为 tail，认为这样遍历完成后，链表自动构成了循环链表了。这是错误的想法，因为如果一开始就设置 tail->right = head，那么遍历二叉树的过程就无法终止了。