# 4-49. 二叉搜索树与双向链表
> 一个有意思的点
# 题目
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点,只能调整树中结点指针的指向。
**注意**:
- 需要返回双向链表最左侧的节点。
例如,输入下图中左边的二叉搜索树,则输出右边的排序双向链表。
![image.png](https://vip2.loli.io/2023/03/27/zUb2M5Cqw7lTRGI.png)
## 思路
利用性质:**二叉搜索树的中序遍历**为`递增序列`
1. 排序链表:节点从小到大,应当使用中序遍历,访问树节点
2. 双向链表:构建相邻节点的引用关系时,设前驱节点 `pre` 和当前节点 `cur`
应当构建 `pre.right = cur`; `cur.left = pre`
3. 循环链表:链表头节点 head 和尾节点 tail,应构建 `head.left = tail` 和 `tail.right = head`
```cpp
// 打印中序遍历
void dfs(Node* root) {
if(root == nullptr) return;
dfs(root->left); // 左
cout << root->val << endl; // 根
dfs(root->right); // 右
}
```
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution
{
public:
TreeNode *head;
TreeNode *pre;
TreeNode *convert(TreeNode *root)
{
dfs(root);
// 如果要构造环
//head ->left = pre;
//pre ->right = head;
return head;
}
void dfs(TreeNode *root)
{
if (!root)
return;
// 根据中序遍历,此时到最左叶节点
dfs(root->left);
// 如果 pre 没有指向任何节点,则说明是在最左叶结点,开始构建链表
// 如果有指向节点,则说明是在构建的过程中
// 要设为空,若不能显示初始化为 nullptr,可以直接声明指针不初始化
if (pre) pre->right = root;
else head = root;
root->left = pre;
pre = root;
dfs(root->right);
}
};
```
# 重点
可以细看下,关于 dfs 循环处理一段
![image.png](https://vip2.loli.io/2023/03/27/y6UZBGdsp4Pq3QO.png)
粗看三者的意义相同,但其实只有中间一段是正确的写法。
## 原因
1. 第一段,将 pre->right = root; 归入 else() 语句,则会导致在 head 安化为 root 之后,pre 得不到初始化,始终为空指针,因此再出现语句 pre->right = root 时,将会报错。
2. 第三段,也是相同的原因。
## 总结
> 思路是在找到最左叶节点时,需要同时将 pre 与 head 节点置于此节点上,再进行递归,但是如何采用 1,3 的写法,当 head 初始化后,pre 并没有得到有效初始化,因此会出现问题。
当然比较质朴的一种写法也是可以的,同时思路更加明晰。
```cpp
if (!pre)
{
head = root;
pre = root;
}
else
{
pre->right = root;
root->left = pre;
pre = root;
}
```