二元查找树转双向链表：程序员面试经典题解析

"这是一份关于程序员面试题目的精选集，包含了100道常见的面试题目，其中重点讨论了如何将二元查找树转化为排序的双向链表的问题。该问题要求在不创建新节点的情况下，仅通过改变节点的指针连接来完成转换。题目给出了两种不同的递归解题思路，并提供了相关数据结构定义和部分代码实现。" 在程序员的面试中，数据结构和算法是重要的考察点。这里提到的"把二元查找树转变成排序的双向链表"是一个经典问题，主要测试应聘者的逻辑思维和对树结构的理解。二元查找树（Binary Search Tree，BST）是一种特殊的树，满足每个节点的左子树上所有节点的值都小于该节点，而右子树上所有节点的值都大于该节点。 **思路一** 是从根节点开始，先递归地处理左子树，使其变为一个排序的左子链表，然后处理右子树，使其变为一个排序的右子链表。在处理完左子树后，我们需要找到左子链表的最大节点，处理完右子树后找到右子链表的最小节点，然后将这三个节点按顺序连接起来。这样从根节点开始，每次处理都会将当前节点插入到已排序的链表中，最终形成完整的排序链表。 **思路二** 利用中序遍历（In-order Traversal）的方法，因为二元查找树的中序遍历结果本身就是有序的。中序遍历的顺序是左子树 -> 节点 -> 右子树，所以在遍历过程中，可以将遍历到的节点依次添加到已有的链表中，从左到右，从而得到排序的链表。 数据结构定义如下： ```cpp struct BSTreeNode { // 二元查找树节点 int m_nValue; // 节点的值 BSTreeNode* m_pLeft; // 左孩子 BSTreeNode* m_pRight; // 右孩子 }; ``` 思路一的代码实现（部分）： ```cpp /////////////////////////////////////////////////////////////////////// // 将子二元查找树转化为排序双向链表 // 输入：pNode - 子树的头节点，asRight - pNode 是否是其父节点的右孩子 // 输出：如果asRight为真，返回子树中的最小节点；否则返回最大节点 /////////// BSTreeNode* ConvertSubBSTreeToSortedDLL(BSTreeNode* pNode, bool asRight) { if (pNode == nullptr) return nullptr; // 递归处理左子树和右子树 BSTreeNode* left = ConvertSubBSTreeToSortedDLL(pNode->m_pLeft, false); BSTreeNode* right = ConvertSubBSTreeToSortedDLL(pNode->m_pRight, true); // 连接左右子树和当前节点 // ...（具体连接代码） return ...; // 返回子树的最大或最小节点 } ``` 这两种方法虽然思路不同，但最终都能达到将二元查找树转换成排序双向链表的目标。在实际编程面试中，理解并掌握这些基础数据结构和算法的转换技巧，对于解决问题和优化代码至关重要。