二叉查找树转排序链表：程序员面试经典题解

"程序员面试100题"是一个专注于帮助求职者准备技术面试的重要资料，特别是针对IT行业，特别关注于C++理论、经典编程题以及面试策略。本篇题目聚焦于将二元查找树（BST）转换为一个排序的双向链表，这在数据结构和算法面试中经常被用来考察候选人的递归思维和对树形数据结构的理解。 题目要求不使用额外节点，仅通过调整现有指针来实现这一转换，体现了对原数据结构操作的深入理解。这里有两种递归解决方案： 1. 思路一：采用自底向上的方法，首先处理左子树，使其形成一个有序的左链表，然后处理当前结点的右子树。关键在于找到左子链表的最右结点和右子树的最左结点，将它们分别与当前结点相连，形成连续的排序链表。这样，从根节点开始递归，直至所有子树都被调整。 2. 思路二：利用中序遍历的思想，确保访问结点时总是按照从小到大的顺序。遍历过程中，每当遇到一个新结点，将其连接到已排序链表的末尾，这样最终得到的就是一个有序的链表。 以下是核心代码示例： ```cpp // 定义二元查找树结点 struct BSTreeNode { int m_nValue; BSTreeNode* m_pLeft; BSTreeNode* m_pRight; }; // 函数1：思路一 - 转换函数 BSTreeNode* convertBST(BSTreeNode* pNode, bool asRight) { // ...（具体递归调用逻辑，包括判断是否为右子节点，递归左右子树并连接链表） } // 函数2：思路二 - 中序遍历并连接链表 BSTreeNode* inorderConvertBST(BSTreeNode* root) { BSTreeNode* prev = nullptr; for (BSTreeNode* curr = root; curr != nullptr; curr = curr->m_pLeft) { // ...（遍历过程中连接结点到链表） } return prev; } ``` 这些代码展示了如何通过递归或中序遍历的方式，利用树的性质来构造排序链表。掌握这类问题有助于提升面试者的算法设计能力和逻辑思维能力，同时在实际工作中处理类似的数据结构问题也会更加得心应手。