Loading... # 4-49. 二叉搜索树与双向链表 > 一个有意思的点 # 题目 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点，只能调整树中结点指针的指向。 **注意**： - 需要返回双向链表最左侧的节点。 例如，输入下图中左边的二叉搜索树，则输出右边的排序双向链表。  ## 思路 利用性质：**二叉搜索树的中序遍历**为`递增序列` 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); // 右 } ``` <div class="panel panel-default collapse-panel box-shadow-wrap-lg"><div class="panel-heading panel-collapse" data-toggle="collapse" data-target="#collapse-504d656fa15c75c668c9f0fac07e690331" aria-expanded="true"><div class="accordion-toggle"><span>参考答案</span> <i class="pull-right fontello icon-fw fontello-angle-right"></i> </div> </div> <div class="panel-body collapse-panel-body"> <div id="collapse-504d656fa15c75c668c9f0fac07e690331" class="collapse collapse-content"> ```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); } }; ``` <div style="height: 15px"></div></div></div></div> # 重点 可以细看下，关于 dfs 循环处理一段  粗看三者的意义相同，但其实只有中间一段是正确的写法。 ## 原因 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; } ``` 最后修改：2023 年 03 月 27 日 10 : 31 PM © 禁止转载 赞赏 如果觉得我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付