微软等面试100题.

### 微软等面试100题：经典算法与数据结构题目解析 #### 把二元查找树转变成排序的双向链表 在本题中，我们要将一棵二元查找树（Binary Search Tree，BST）转换为一个排序的双向链表（Doubly Linked List）。目标是利用树中的节点来构建链表，而无需创建任何新的节点。 **题目背景与要求**： - 输入：一棵二元查找树。 - 输出：转换后的排序双向链表。 - 限制：不创建新节点，只调整节点间的指针指向。 **数据结构定义**： ```c++ struct BSTreeNode { int m_nValue; // 节点值 BSTreeNode* m_pLeft; // 左子节点指针 BSTreeNode* m_pRight; // 右子节点指针 }; ``` **解决思路**： 此问题可以通过递归方式解决，核心在于中序遍历树的节点，并在遍历过程中构建链表。对于每个节点，我们递归地连接由其左子树和右子树形成的两个双向链表，形成一个完整的链表。 **代码实现**： ```c++ BSTreeNode* treeToLinkedList(BSTreeNode* root) { BSTreeNode* head, *tail; helper(head, tail, root); return head; } void helper(BSTreeNode*& head, BSTreeNode*& tail, BSTreeNode* root) { BSTreeNode* lt, *rh; if (root == NULL) { head = NULL; tail = NULL; return; } helper(head, lt, root->m_pLeft); // 处理左子树 helper(rh, tail, root->m_pRight); // 处理右子树 if (lt != NULL) { // 如果左子树存在 lt->m_pRight = root; root->m_pLeft = lt; } else { head = root; // 当前节点成为链表头部 } if (rh != NULL) { // 如果右子树存在 root->m_pRight = rh; rh->m_pLeft = root; } else { tail = root; // 当前节点成为链表尾部 } } ``` #### 设计包含min函数的栈 本题要求设计一个特殊的栈数据结构，其中包含一个`min`函数，可以返回栈中最小元素。此外，所有基本操作（`push`、`pop` 和 `min`）的时间复杂度都应为 O(1)。 **解决思路**： 为了实现这一功能，我们可以维护两个栈：一个用于存储常规元素（`data`栈），另一个用于跟踪当前栈中的最小值（`min`栈）。每当有新元素加入时，除了将其压入`data`栈之外，还要检查这个元素是否小于或等于`min`栈的顶部元素，如果是，则也压入`min`栈。 **数据结构定义与实现**： ```c++ struct MinStackElement { int data; int min; }; struct MinStack { MinStackElement* data; MinStackElement* min; int size; int topData; int topMin; }; MinStack MinStackInit(int maxSize) { MinStack stack; stack.size = maxSize; stack.data = (MinStackElement*)malloc(sizeof(MinStackElement) * maxSize); stack.min = (MinStackElement*)malloc(sizeof(MinStackElement) * maxSize); stack.topData = 0; stack.topMin = 0; return stack; } void MinStackFree(MinStack stack) { free(stack.data); free(stack.min); } void MinStackPush(MinStack& stack, int d) { if (stack.topData == stack.size) error("out of stack space."); stack.data[stack.topData].data = d; stack.data[stack.topData].min = (stack.topData == 0 ? d : stack.min[stack.topMin - 1]); if (stack.data[stack.topData].min > d) stack.data[stack.topData].min = d; stack.topData++; if (stack.topMin == 0 || stack.min[stack.topMin - 1] >= d) stack.min[stack.topMin++] = d; } int MinStackPop(MinStack& stack) { if (stack.topData == 0) error("stack is empty!"); stack.topData--; return stack.data[stack.topData].data; } int MinStackMin(MinStack& stack) { if (stack.topMin == 0) error("stack is empty!"); return stack.min[stack.topMin - 1]; } ``` 通过以上设计，我们成功实现了所需功能，同时保持了 O(1) 的时间复杂度。