面试题21：包含min函数的栈
定义一个数据结构，请在该类型中实现一个能够得到栈中最小元素的min函数。在该栈中，调用min，push以及pop的时间复杂度都是o(1)。
leetcode链接： https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/class MinStack { public: /** initialize your data structure here. */ stack<int> s1; stack<int> s2; MinStack() { } void push(int x) { s1.push(x); if (s2.empty()) { s2.push(x); return; } int tmp = s2.top(); if (x < tmp) { s2.push(x); } else { s2.push(tmp); } } void pop() { s1.pop(); s2.pop(); } int top() { return s1.top(); } int getMin() { return s2.top(); } }; /** * Your MinStack object will be instantiated and called as such: * MinStack* obj = new MinStack(); * obj->push(x); * obj->pop(); * int param_3 = obj->top(); * int param_4 = obj->getMin(); */
解题思路：一个正常栈，一个辅助栈。辅助栈与正常栈同步进出。辅助栈判断新入栈元素和当前栈顶元素大小，当大于栈顶元素，仍压入栈顶元素，因为此时最小值不变。当小于栈顶元素，压入当前元素。
分析栈内压入3，4，2，1之后连续两次弹出，再压入0时数据栈状态
| 步骤 | 操作 | 数据栈 | 辅助栈 | 最小值 |
|---|---|---|---|---|
| 1 | 压入3 | 3 | 3 | 3 |
| 2 | 压入4 | 34 | 33 | 3 |
| 3 | 压入2 | 342 | 332 | 2 |
| 4 | 压入1 | 3421 | 3321 | 1 |
| 5 | 弹出 | 342 | 332 | 2 |
| 6 | 弹出 | 34 | 33 | 3 |
| 7 | 压入0 | 340 | 330 | 0 |
面试题22：栈的压入，弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为栈的弹出顺序。假设压入栈的数字君不相等。
leetcode链接 https://leetcode-cn.com/problems/validate-stack-sequences/class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> tmp; int popNumber = 0; for(int i = 0; i < pushed.size(); i++) { if (pushed[i] != popped[popNumber]) { tmp.push(pushed[i]); } else { popNumber++; while(true) { if (tmp.empty()) { break; } if (popped[popNumber] == tmp.top()) { tmp.pop(); popNumber++; } else { break; } } } } for(int i = popNumber; i < popped.size(); i++) { if (tmp.top() != popped[popNumber]) { return false; } tmp.pop(); } return true; } };
解题思路：用一个辅助栈。按入栈数组顺序入栈，当当前入栈元素为要弹出数组中第一个元素，不入栈，同时判断栈顶和出栈数组中第二个元素，若相同出栈。后面元素同理。若不同，继续入栈。此时，出栈数组应理解为减去刚刚已出栈元素之后的数组。当元素全部入栈后，再将栈弹出，与出栈数组进行比对，完全吻合，则为true。
面试题23：从上到下打印二叉树
从上到下打印二叉树的每个节点，每一层按从左往右顺序进行打印
牛客链接 https://www.nowcoder.com/practice/7fe2212963db4790b57431d9ed259701?tpId=13&&tqId=11175&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> result; if (root == NULL) { return result; } queue<TreeNode*> tree; tree.push(root); while(!tree.empty()) { result.push_back(tree.front()->val); if (tree.front()->left) { tree.push(tree.front()->left); } if (tree.front()->right) { tree.push(tree.front()->right); } tree.pop(); } return result; } };
解题思路：树的层次遍历，属于广度优先遍历。用队列。
本题扩展：遍历有向图，没找到链接，不想写构建图，先不写了。思路个二叉树一样。
面试题24：二叉搜索树的后序遍历序列
输入某数组，判断该数组是不是某二叉搜索树的后序遍历
leetcode链接 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/class Solution { public: bool verifyPostorder(vector<int>& postoerder, int begin, int end) { if (begin >= end) { return true; } int root = postoerder[end]; int i = begin; for(;i <= end - 1; i++) { if (postoerder[i] >= root) // 找到左右子树分界点 { break; } } int sed = i; for(; i <= end - 1; i++) { if (postoerder[i] <= root) // 发现本应是右子树的序列有小于根的元素 { return false; } } bool left = true, right = true; left = verifyPostorder(postoerder, begin, sed - 1); right = verifyPostorder(postoerder, sed, end - 1); return left && right; } bool verifyPostorder(vector<int>& postorder) { if (postorder.size() == 0) { return true; } return verifyPostorder(postorder, 0, postorder.size() - 1); } };
解题思路：对于二叉搜索树，其特性为左节点小于根节点，右节点大于根节点。后序遍历的遍历顺序为左右根。结合来看，比如当前输入数组为{5,7,6,9,11,10,8},可判断根节点为8，左子树对应序列为{5,7,6},右子树对应序列为{11,10,8}，递归调用建立左右子树，建立过程同上。当递归到某个序列，发现无法找到小于根节点和大于根节点的分解点时，即为该数组不合法。
相关题目：输入一个整数数组，判断该数组是不是某二叉搜索树的前序遍历
没找到链接，也不写了。思路是前序遍历是根左右。因为第一个元素是根，从第二个元素开始判断，小于根的子序列就是左子树，大于根的子序列就是右子树，利用递归，进行树的重建。当找不到左右子树分界点，代表数组不合法。
当处理一个二叉树遍历序列，基本思路为找到根节点，并由此推出左右子树子序列，利用递归进行重建
面试题25：二叉树中和为某一值的路径
输入一个二叉树和一个整数，打印出二叉树中节点值的和胃输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
leecode链接 https://leetcode-cn.com/problems/path-sum-ii//** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: void pathSum(TreeNode* root, vector<vector<int>>& result, stack<int>& curPath, int& curSum, const int sum) { if (root == NULL) { return; } if (root->left == NULL && root->right == NULL) { // cout << "leef: " << root->val << " cur: " << curSum << endl; if (curSum + root->val == sum) { // cout << "here" << endl; vector<int> tmp; stack<int> tmpStack; tmpStack = curPath; tmp.push_back(root->val); while(!tmpStack.empty()) { tmp.push_back(tmpStack.top()); tmpStack.pop(); } vector<int> path; for(int i = tmp.size() - 1; i >= 0; i--) { path.push_back(tmp[i]); } result.push_back(path); } else { return; } } curSum = curSum + root->val; curPath.push(root->val); if (root->left) { pathSum(root->left, result, curPath, curSum, sum); } if (root->right) { pathSum(root->right, result, curPath, curSum, sum); } curPath.pop(); curSum = curSum - root->val; // 注意返回父节点前，要清当前节点 return; } vector<vector<int>> pathSum(TreeNode* root, int sum) { vector<vector<int>> result; int curSum = 0; stack<int> curPath; // 栈这个结构其实选的不太好，中间保存的时候倒了两遍，影响了效率，其实可以直接用vector，暂时懒得改，后续再说 pathSum(root, result, curPath, curSum, sum); return result; } };
解题思路：前序遍历。递归时带着当前路径加和，每当遇到叶子节点，判断当前和+叶子节点值是否等于目标num，若等于，把当前路径push进result，若不等于，舍弃。递归返回叶子节点父节点，对另外一面进行判断。注意遍历完节点左右子树，要把该节点value从sum和路径中删除，之后再返回其父节点。
