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

在程序员面试中，一道常见的题目是将二元查找树(BST, Binary Search Tree)转换成一个排序的双向链表，而这个过程不允许创建新的节点，仅通过调整节点指针。这道题目源自微软的面试题库，主要考察候选人的递归思维和数据结构处理能力。 解题思路主要有两种： 1. **递归思路一**：从根节点开始，递归地处理左右子树。首先，对左子树进行调整，使其成为一个有序的左链表，然后找到左链表的最右节点和当前节点，将它们连接起来。接着，对右子树做同样的操作，但这次将右子链表的最左节点与当前节点相连。这样，每次递归都会确保链表顺序正确。 2. **中序遍历思路**：另一种方法是中序遍历整个二叉查找树，按照从小到大的顺序访问结点。每当访问到一个结点时，由于前面的结点已经被调整好，可以将当前结点插入到已排序链表的末尾。遍历结束后，整个树就被转换成了一个有序的链表。 以下是参考代码部分的示例，展示了如何定义BST节点结构以及实现这两种思路的代码片段： ```cpp // 定义二元查找树结点 struct BSTreeNode { int m_nValue; // 节点值 BSTreeNode* m_pLeft; // 左孩子 BSTreeNode* m_pRight; // 右孩子 }; // 递归思路一 BSTreeNode* convertBSTToDoublyLinkedList(BSTreeNode* pNode, bool asRight) { if (pNode == nullptr) return nullptr; // 对左子树进行调整 BSTreeNode* sortedLeft = convertBSTToDoublyLinkedList(pNode->m_pLeft, false); // ... (连接左右子链表) } // 中序遍历思路 BSTreeNode* inorderConvertBSTToDoublyLinkedList(BSTreeNode* root) { BSTreeNode* dummyHead = new BSTreeNode(); // 创建虚拟头节点 BSTreeNode* prev = dummyHead; function<void(BSTreeNode*)> inorder = [&](BSTreeNode* node) { if (node == nullptr) return; inorder(node->m_pLeft); // 先遍历左子树 prev->m_pRight = node; // 将当前结点链接到链表 prev = node; // 更新prev为当前结点 inorder(node->m_pRight); // 再遍历右子树 }; inorder(root); dummyHead->m_pRight->m_pLeft = nullptr; // 断开虚拟头节点与实际链表的连接 return dummyHead->m_pRight; } ``` 这两者都能有效地将二元查找树转换成排序的双向链表，但是递归思路可能更直观，而中序遍历则展示了链表构建的过程。掌握这类问题的关键在于理解树的性质，以及如何利用递归或迭代的方式进行结构转换。在面试中，除了提供代码解决方案外，面试官还会关注你对算法的理解、复杂度分析和错误处理能力。