微软等公司数据结构+算法面试100_前40(附答案)

### 数据结构转换：二叉搜索树到排序双向链表 #### 题目解析与解决方案 **题目描述：** 输入一棵二元查找树（即二叉搜索树，Binary Search Tree, BST），将其转换为一个排序的双向链表。转换过程中不能创建任何新的节点，只能通过调整现有节点的指针来实现。 **解题思路：** 为了将二叉搜索树转换为排序的双向链表，我们可以利用中序遍历的思想。中序遍历的特点是按照左根右的顺序访问节点，这正好符合二叉搜索树节点值的升序排列。因此，我们可以利用递归或迭代的方法进行中序遍历，并在遍历的过程中调整每个节点的左右指针，将其转化为双向链表中的前后指针。 **具体步骤如下：** 1. **初始化：** 定义两个指针 `pHead` 和 `pListIndex`，分别用于记录双向链表的头节点和当前操作的最后一个节点。 2. **构建二叉搜索树：** 使用 `addBSTreeNode` 函数构建一棵二叉搜索树。 3. **中序遍历：** 调用 `ergodicBSTree` 函数对二叉搜索树进行中序遍历，在遍历过程中调用 `convertToDoubleList` 函数完成二叉搜索树向双向链表的转换。 4. **转换过程：** - 在每次遍历时，当前节点 `pCurrent` 的左指针 `m_pLeft` 指向前一个节点 `pListIndex`； - 如果 `pListIndex` 不为空，则 `pListIndex` 的右指针 `m_pRight` 指向当前节点 `pCurrent`； - 更新 `pListIndex` 为当前节点 `pCurrent`； - 如果是第一个节点，则更新 `pHead` 为当前节点 `pCurrent`。 #### 代码示例 ```cpp struct BSTreeNode { int m_nValue; // value of node BSTreeNode* m_pLeft; // left child of node BSTreeNode* m_pRight; // right child of node }; typedef BSTreeNode DoubleList; DoubleList* pHead = nullptr; DoubleList* pListIndex = nullptr; void convertToDoubleList(BSTreeNode* pCurrent); // 创建二叉搜索树 void addBSTreeNode(BSTreeNode*& pCurrent, int value) { if (nullptr == pCurrent) { BSTreeNode* pBSTree = new BSTreeNode(); pBSTree->m_pLeft = nullptr; pBSTree->m_pRight = nullptr; pBSTree->m_nValue = value; pCurrent = pBSTree; } else { if ((pCurrent->m_nValue) > value) { addBSTreeNode(pCurrent->m_pLeft, value); } else if ((pCurrent->m_nValue) < value) { addBSTreeNode(pCurrent->m_pRight, value); } } } // 遍历二叉搜索树 void ergodicBSTree(BSTreeNode* pCurrent) { if (nullptr == pCurrent) return; if (nullptr != pCurrent->m_pLeft) { ergodicBSTree(pCurrent->m_pLeft); } convertToDoubleList(pCurrent); if (nullptr != pCurrent->m_pRight) { ergodicBSTree(pCurrent->m_pRight); } } // 二叉搜索树转换为双向链表 void convertToDoubleList(BSTreeNode* pCurrent) { pCurrent->m_pLeft = pListIndex; if (nullptr != pListIndex) { pListIndex->m_pRight = pCurrent; } else { pHead = pCurrent; } pListIndex = pCurrent; } int main() { BSTreeNode* pRoot = nullptr; pListIndex = nullptr; pHead = nullptr; addBSTreeNode(pRoot, 10); addBSTreeNode(pRoot, 4); addBSTreeNode(pRoot, 6); addBSTerrno(pRoot, 8); addBSTreeNode(pRoot, 12); addBSTreeNode(pRoot, 14); addBSTreeNode(pRoot, 15); addBSTreeNode(pRoot, 16); ergodicBSTree(pRoot); return 0; } ``` ### 设计包含 min 函数的栈 #### 题目解析与解决方案 **题目描述：** 设计一个栈，除了常规的 `push` 和 `pop` 操作外，还需要支持一个额外的操作 `min`，能够返回栈中的最小元素。要求这三个操作的时间复杂度都为 O(1)。 **解题思路：** 为了保证 `min` 操作的时间复杂度为 O(1)，我们需要维护一个辅助栈来存储当前栈中的最小值。每当有新元素入栈时，如果该元素小于等于当前最小值，则同时将该元素推入辅助栈；出栈时，如果弹出的元素等于当前最小值，则同时弹出辅助栈中的元素。这样，无论栈中元素如何变化，辅助栈顶部始终是最小值。 #### 代码示例 ```cpp class MinStack { private: std::stack<int> dataStack; std::stack<int> minStack; public: // 构造函数 MinStack() {} // 添加元素 void push(int x) { dataStack.push(x); if (minStack.empty() || x <= minStack.top()) { minStack.push(x); } } // 删除元素 void pop() { if (dataStack.top() == minStack.top()) { minStack.pop(); } dataStack.pop(); } // 获取最小元素 int getMin() { return minStack.top(); } }; int main() { MinStack s; s.push(3); s.push(2); s.push(1); s.push(4); s.push(0); std::cout << "Minimum: " << s.getMin() << std::endl; // 输出 0 s.pop(); std::cout << "Minimum: " << s.getMin() << std::endl; // 输出 1 return 0; } ``` 这两个题目展示了二叉搜索树到排序双向链表的转换方法以及设计包含 `min` 函数的栈的具体实现细节。通过上述代码示例，我们可以清晰地理解这些数据结构和算法的应用场景及实现原理。