二元查找树转排序双向链表：面试经典100题解

在程序员面试题精选100题中，第1题要求将一个二元查找树转换成一个排序的双向链表，这是一个经典的算法问题，常用于评估应聘者的递归思维和数据结构理解能力。题目给出的场景是将一棵具有以下结构的二叉查找树： ``` 10 / \ 6 14 / \ / \ 4 8 12 16 ``` 转换成有序的双向链表形式，即：4 -> 6 -> 8 -> 10 -> 12 -> 14 -> 16。 解决这个问题有多种方法，这里介绍两种常见的递归策略： 1. 思路一：递归调整子树 递归的核心思想是，从根节点开始，先递归地处理左子树，将其转换为排序链表，然后将左子链表的最右边元素（最大值）链接到当前节点，接着递归处理右子树。最后，连接当前节点和右子链表的最左边元素（最小值）。这个过程会确保链表始终保持递增顺序。 2. 思路二：中序遍历 另一种方法是采用中序遍历，这是一种自底向上的方法。从最低层节点开始，按升序访问每个节点。每次访问新节点时，将其链接到已排序链表的末尾，这样整个过程下来，链表自然会保持排序状态。 下面是思路一的代码示例，用于实现将二叉查找树转换为排序双链表： ```cpp struct BSTreeNode { int m_nValue; BSTreeNode* m_pLeft; BSTreeNode* m_pRight; }; void convertBSTToSortedList(BSTreeNode* pNode, bool asRight) { // ... 实现递归逻辑，包括左子树、右子树的调整和链接 } BSTreeNode* convertBST(BSTreeNode* root) { if (!root) return nullptr; convertBSTToSortedList(root, true); // 根节点默认为右孩子 // 递归处理父节点，连接左右子链表 // 返回排序后的根节点 } ``` 思路二的代码实现需要对中序遍历进行调整，并根据已排序链表的头节点插入新节点，但核心逻辑与思路一类似。这两种方法在实际编程面试中都是非常重要的技能，能够展示出程序员对数据结构如二叉查找树以及排序算法的深入理解和应用能力。通过这道题目，面试官可以考察应聘者是否具备良好的逻辑思维、递归调用和链表操作技巧。