二元查找树转排序双向链表的面试题解析

"这篇资源是关于程序员面试题的精选合集，主要聚焦于编码技能，特别是涉及二元查找树转化为排序双向链表的问题。" 在编程面试中，掌握各种数据结构和算法是至关重要的，本资源提供的面试题精选100则强调了这一要点。其中，有一道题目要求将一个二元查找树（Binary Search Tree, BST）转换成一个排序的双向链表（Sorted Doubly Linked List），这个题目源自微软的面试。这不仅考验程序员对二元查找树的理解，还考察了他们如何利用递归或迭代策略解决复杂问题的能力。 二元查找树是一种特殊的树结构，其中每个节点的左子树只包含比它小的节点，而右子树包含比它大的节点。双向链表则是一种可以双向遍历的线性数据结构。将二元查找树转化为排序双向链表的关键在于保持原有的顺序关系。 本题提供了两种递归解法： 1. 思路一：自底向上处理。首先，递归地将左子树转换为有序链表，然后将当前节点与左子链表的最大节点连接起来。接着，递归处理右子树，将其转换为有序链表，并将当前节点与右子链表的最小节点连接起来。从根节点开始，逐步调整所有节点，直到整个树被处理完毕。 2. 思路二：中序遍历。中序遍历能确保按从小到大的顺序访问节点。每次访问到一个新的节点，就将其插入到已形成的链表末尾。遍历完整棵树后，所有节点将构成一个排序的双向链表。 为了实现这个转换，我们需要定义二元查找树节点的数据结构，如以下示例所示： ```cpp struct BSTreeNode { int m_nValue; // 节点的值 BSTreeNode* m_pLeft; // 左子节点 BSTreeNode* m_pRight; // 右子节点 }; ``` 思路一对应的代码可能如下： ```cpp BSTreeNode* ConvertBSTToDLL(BSTreeNode* pNode, bool asRight) { if (pNode == nullptr) return nullptr; // 递归处理左右子树 pNode->m_pLeft = ConvertBSTToDLL(pNode->m_pLeft, true); pNode->m_pRight = ConvertBSTToDLL(pNode->m_pRight, false); // 链接节点 if (asRight) { // 如果当前节点是其父节点的右子节点，链接到前一个最大节点 BSTreeNode* prevMax = nullptr; while (pNode->m_pLeft != nullptr) { prevMax = pNode->m_pLeft; pNode->m_pLeft = prevMax->m_pRight; prevMax->m_pRight = pNode; pNode = prevMax; } } else { // 如果当前节点是其父节点的左子节点，链接到后一个最小节点 BSTreeNode* nextMin = nullptr; while (pNode->m_pRight != nullptr) { nextMin = pNode->m_pRight; pNode->m_pRight = nextMin->m_pLeft; nextMin->m_pLeft = pNode; pNode = nextMin; } } return asRight ? pNode : pNode->m_pRight; } ``` 通过这样的转换，可以将原二元查找树中的数据结构优化为双向链表，便于进行顺序操作，例如在链表中进行查找、插入和删除等操作。这道题目不仅有助于提升编程能力，还能帮助面试者更好地理解数据结构之间的转换及其在实际问题中的应用。