剑指 Offer 36. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。 为了让您更好地理解问题，以下面的二叉搜索树为例： 我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。 下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

DFS（中序遍历）

思路

二叉搜索树转化为单向增顺链表时，遍历顺序为【左-根-右】，和二叉树的中序遍历一致，如下

//二叉树遍历,原地转换为单向链表
pre=NULL;
dfs(root->left);//向左遍历
if(pre) pre->right=root;
root->left=NULL;//删除前驱
pre=root;
dfs(root->right);

基于上述基础，题目提出了以下更多需求：

• 双向链表
• head指针指向整个序列中最小的节点
• 头尾循环

双向链表：

//如下实现前后驱之间的双向
//pre为前驱，cur为当前出栈的节点
pre->right=cur;
cur->left=pre;
pre=cur;//更新下一个前驱

head指针指向整个序列中最小的节点：
在向左遍历时不断更新head节点为当前节点，直到到达最左侧时不再更新，故需要一个判定条件，即pre!=NULL时，不再更新。显然由于到最左节点时,pre更新；
头尾循环：
当搜索树遍历完成时,pre指向最后一个节点,head指向第一个节点，实现pre与head之间的循环即可。

算法

实现

typedef Node* pointer;
pointer pre=NULL,head=NULL;
void dfs(Node* cur){
    if(!cur) return;
    dfs(cur->left);
    if(pre) pre->right=cur;
    else head=cur;
    cur->left=pre;
    pre=cur;
    dfs(cur->right);
}
Node* treeToDoublyList(Node* root) {
    if(root==NULL) return NULL;
    dfs(root);
    pre->right=head;
    head->left=pre;
    return head;
}

复杂度分析

• 时间复杂度:
• 空间复杂度:

题目标题难度划分

算法掌握难度程度划分