程序员面试题精选100题

【知识点详解】 在程序员面试中，经常会遇到与数据结构和算法相关的题目，特别是涉及二元查找树（Binary Search Tree, BST）的转换问题。这里提到的"把二元查找树转变成排序的双向链表"是一道经典的面试题，旨在考察应聘者的递归思维和对数据结构的理解。 二元查找树是一种特殊的树形数据结构，其中每个节点包含一个键（key）、一个关联的值、一个指向左子树的引用和一个指向右子树的引用。左子树上的所有节点的键都小于当前节点的键，右子树上的所有节点的键都大于当前节点的键。双向链表则是一种线性数据结构，每个节点包含两个指针，分别指向其前一个和后一个节点，使得链表中的元素可以双向遍历。 **转换方法一：递归法** 1. **递归基**：如果节点为空，返回NULL。 2. **递归步骤**： - 对左子树进行递归转换，得到排序链表的尾部节点（左子树的最大节点）。 - 将当前节点的左指针指向左子树的尾部节点。 - 对右子树进行递归转换，得到排序链表的头部节点（右子树的最小节点）。 - 如果右子树非空，将当前节点的右指针指向右子树的头部节点，并让右子树的头部节点的左指针指向当前节点。 递归过程从根节点开始，每次递归都会调整子树的结构，直到所有节点都被处理，最后形成一个排序的双向链表。 **转换方法二：中序遍历法** 1. **中序遍历**：二元查找树的中序遍历顺序是升序的，即先遍历左子树，然后访问根节点，最后遍历右子树。 2. **链表构建**：在遍历过程中，将每个访问过的节点链接到已遍历过的链表末尾。 中序遍历的过程中，由于访问顺序是从小到大，所以可以保证每次插入新节点时，链表已经是有序的。当遍历完所有节点后，整个树就转换成了一个排序的双向链表。 以下是对应代码的简化版： ```cpp struct BSTreeNode { int m_nValue; BSTreeNode* m_pLeft; BSTreeNode* m_pRight; }; BSTreeNode* convertBSToDLL(BSTreeNode* root) { if (!root) return nullptr; stack<BSTreeNode*> s; BSTreeNode* prev = nullptr; while (root || !s.empty()) { while (root) { s.push(root); root = root->m_pLeft; } root = s.top(); s.pop(); if (prev) { prev->m_pRight = root; root->m_pLeft = prev; } else { prev = root; } root = root->m_pRight; } return prev; } ``` 以上代码利用了栈辅助中序遍历，避免了递归调用的开销，同时构建了排序的双向链表。 在实际面试中，解这类问题的关键在于理解二元查找树和双向链表的特性，以及如何通过操作指针来转换它们。掌握这些技巧不仅有助于解决这道题，还能够帮助理解其他数据结构转换问题，如平衡二叉树转换为数组等。对于程序员来说，理解和熟练运用这些基础数据结构和算法是必不可少的能力，能够在面试中展现自己的技术实力。