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

“程序员面试题精选100题” 在编程面试中，掌握各种算法和数据结构是至关重要的，其中二元查找树转双向链表是一个常见的面试题。这道题目要求将给定的二元查找树（BST）转换成一个有序的双向链表，而且不允许创建新的节点，只能修改原有节点的指针。 二元查找树是一种特殊的二叉树，满足每个节点的左子树只包含小于节点值的节点，右子树只包含大于节点值的节点。这种特性使得二元查找树具有良好的查找性能。在转换为双向链表的过程中，我们需要保持原有的顺序关系，即链表中的节点值应按升序排列。 **思路一** 的递归方法是自底向上处理，首先处理左子树，然后处理右子树。在处理每个节点时，将左子树的最大节点、当前节点和右子树的最小节点连接起来。具体步骤如下： 1. 递归地将左子树转换为排序的左子链表。 2. 将左子链表的最后一个节点（最大节点）的右指针指向当前节点。 3. 当前节点的左指针指向左子链表的最后一个节点。 4. 递归地将右子树转换为排序的右子链表。 5. 将当前节点的右指针指向右子链表的第一个节点（最小节点）。 6. 如果当前节点不是根节点，则将右子链表的第一个节点的左指针指向当前节点的父节点。 **思路二** 是通过中序遍历实现，即左子树-根节点-右子树的顺序访问。在遍历过程中，将每个节点添加到已排序的链表末尾。遍历完成后，所有节点都将构成有序链表。中序遍历的特点是会按照升序访问所有节点，所以适合构建排序链表。 以下是对应代码的伪代码： ```cpp // 定义二元查找树节点 struct BSTreeNode { int m_nValue; BSTreeNode* m_pLeft; BSTreeNode* m_pRight; }; // 思路一的递归实现 BSTreeNode* convertBSToDLL(BSTreeNode* pNode, bool asRight) { // ... 实现递归逻辑 ... } // 思路二的中序遍历实现 void inorderTraversal(BSTreeNode* pNode, BSTreeNode*& pHead, BSTreeNode*& pTail) { if (pNode == nullptr) return; inorderTraversal(pNode->m_pLeft, pHead, pTail); if (pHead == nullptr) { pHead = pNode; pTail = pNode; } else { pTail->m_pRight = pNode; pNode->m_pLeft = pTail; pTail = pNode; } inorderTraversal(pNode->m_pRight, pHead, pTail); } ``` 这两个方法都可以有效地解决问题，但思路二可能更为直观，因为它仅需一次遍历，而思路一需要递归处理每个子树。在实际面试中，应根据问题的具体要求和时间复杂度要求选择合适的方法。理解这两种方法有助于提升对树结构和递归问题的处理能力，对于程序员来说，这是面试和工作中必须掌握的基本技能。