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

"程序员面试经典100题" 在软件开发领域，面试是评估候选人技能和知识的重要环节。《程序员面试经典100题》是一本备受推崇的资料，它涵盖了华为、中兴等知名公司面试中可能出现的问题，对于准备面试的程序员来说，这本书提供了宝贵的实践练习。 其中一道典型的面试题是关于将二元查找树（Binary Search Tree, BST）转换为排序的双向链表。这道题目要求在不创建新节点的情况下，仅通过调整原有节点的指针，将一棵BST转换成一个有序的双向链表。 二元查找树是一种特殊的树结构，每个节点的左子树上的所有节点值都小于该节点，而右子树上的所有节点值都大于该节点。双向链表则是一种链式存储结构，每个节点包含指向前后节点的指针。 转换方法可以分为两种主要思路： **思路一：自底向上递归** 1. 首先，递归处理左子树，将其转换为一个排序的左子链表。 2. 然后，递归处理右子树，将其转换为一个排序的右子链表。 3. 当处理到当前节点时，将左子链表的最大节点（即左子树的最后一个节点）与当前节点连接，同时将当前节点与右子链表的最小节点（即右子树的第一个节点）连接。 4. 从根节点开始，依次处理所有节点。 **思路二：中序遍历** 1. 使用中序遍历的方式访问树中的节点，因为二元查找树的中序遍历结果就是排序后的序列。 2. 每访问到一个节点，假设之前的节点已经形成一个排序链表，将当前节点添加到链表的末尾。 3. 继续遍历，直到所有节点都被处理，最终整个树将转换为排序的双向链表。 以下是对应的C++代码实现（以思路一为例）： ```cpp struct BSTreeNode { int m_nValue; BSTreeNode* m_pLeft; BSTreeNode* m_pRight; }; // 转换函数 BSTreeNode* ConvertBSTToSortedDLL(BSTreeNode* pNode, bool asRight) { // 递归处理左子树 if (pNode->m_pLeft != nullptr) { pNode->m_pLeft = ConvertBSTToSortedDLL(pNode->m_pLeft, true); } // 处理当前节点 BSTreeNode* pPrev = nullptr; if (!asRight) { // 如果不是右子节点，那么前一个节点是左子树的最大节点 while (pNode->m_pLeft != nullptr) { pPrev = pNode->m_pLeft; pNode->m_pLeft = pPrev->m_pRight; pPrev->m_pRight = pNode; pNode = pPrev; } } else { // 如果是右子节点，找到上一个节点 while (pNode->m_pRight != nullptr) { pPrev = pNode->m_pRight; pNode->m_pRight = pPrev->m_pLeft; pPrev->m_pLeft = pNode; pNode = pPrev; } } // 递归处理右子树 if (pNode->m_pRight != nullptr) { pNode->m_pRight = ConvertBSTToSortedDLL(pNode->m_pRight, false); } return pNode; } ``` 这道题目考察了对数据结构的理解，尤其是树和链表的特性，以及如何利用递归解决问题的能力。在面试中，这样的问题能够有效地测试候选人的逻辑思维、问题解决和编程能力。通过理解和掌握这种转换方法，程序员不仅可以提高面试成功的机会，还能在实际工作中更好地处理数据结构的转换和优化问题。