2011年程序员面试试题宝典100题_附程序

### 2011年程序员面试试题宝典之二叉查找树转换为排序双向链表 在《2011年程序员面试试题宝典100题》中，有一道经典的算法题：“把二元查找树转变成排序的双向链表”。这道题目考察了程序员对数据结构和算法的理解深度，尤其是对于树形结构与链表之间的转换能力。 #### 题目解析 题目要求将给定的二叉查找树（Binary Search Tree，BST）转换为一个排序的双向链表，且不创建任何新的节点，只调整现有节点的指针指向。例如，给定以下二叉查找树： ``` 10 / \ 6 14 / \ / \ 4 8 12 16 ``` 转换后应成为排序的双向链表： ``` 4 <-> 6 <-> 8 <-> 10 <-> 12 <-> 14 <-> 16 ``` #### 解题思路 解题关键在于利用二叉查找树的性质和递归方法。二叉查找树的中序遍历序列是升序排列的，因此，通过中序遍历可以自然地构造出排序的双向链表。 **思路一：自底向上调整** 1. **左子树调整**：递归地调整左子树，使其转换成一个排序的双向链表。 2. **连接左右子树**：将调整后的左子树的最右节点连接到当前节点，当前节点的左指针指向左子树的最右节点。 3. **右子树调整**：递归地调整右子树，使其转换成一个排序的双向链表。 4. **连接当前节点与右子树**：将当前节点的右指针指向右子树的最左节点，右子树的最左节点的左指针指向当前节点。 **思路二：中序遍历构建** 1. **初始化**：设定一个全局变量`prev`记录前一个访问的节点。 2. **中序遍历**：采用中序遍历方式访问每个节点，每次访问节点时，都将`prev`与当前节点进行双向链接，即当前节点的左指针指向`prev`，`prev`的右指针指向当前节点。 3. **更新`prev`**：访问完当前节点后，将`prev`设置为当前节点，继续中序遍历直到所有节点被访问。 #### 参考代码示例 ```cpp struct BSTreeNode { int m_nValue; BSTreeNode *m_pLeft; BSTreeNode *m_pRight; }; BSTreeNode* ConvertNode(BSTreeNode* pNode, bool asRight) { // 递归基 if (!pNode) return NULL; BSTreeNode *pLeft = NULL, *pRight = NULL; // 调整左子树 if (pNode->m_pLeft) pLeft = ConvertNode(pNode->m_pLeft, false); // 连接左子树最大节点与当前节点 if (pLeft) { pLeft->m_pRight = pNode; pNode->m_pLeft = pLeft; } // 调整右子树 if (pNode->m_pRight) pRight = ConvertNode(pNode->m_pRight, true); // 连接当前节点与右子树最小节点 if (pRight) { pNode->m_pRight = pRight; pRight->m_pLeft = pNode; } BSTreeNode *pTemp = pNode; // 根据节点是否为父节点的右子节点返回相应端点 if (asRight) { while (pTemp->m_pLeft) pTemp = pTemp->m_pLeft; } else { while (pTemp->m_pRight) pTemp = pTemp->m_pRight; } return pTemp; } ``` 这段代码实现了上述“思路一”中的逻辑，通过递归地调整左右子树，并在适当位置连接节点，最终完成二叉查找树向排序双向链表的转换。此题不仅考验了算法设计能力，还要求对数据结构有深刻理解，是程序员面试中常见的经典问题之一。