面试题21：包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。

解答：代码如下：

stack<int> ValSta; stack<int> MinSta; void push(int value) { ValSta.push(value); if(MinSta.empty() || (!MinSta.empty() && value < MinSta.top())) { MinSta.push(value); } else { MinSta.push(MinSta.top()); } } void pop() { if(!ValSta.empty()) { ValSta.pop(); } if(!MinSta.empty()) { MinSta.pop(); } } int top() { if(!!ValSta.empty()) { return ValSta.top(); } } int min() { if(!MinSta.empty()) { return MinSta.top(); } }

面试题22：栈的压入、弹出序列

题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出序列。假设压入栈的所有数字均不相等。例如序列1、2、3、4、5是某栈的压栈序列，序列4、5、3、2、1是该压栈序列对应的一个弹出序列，但4、3、5、1、2就不可能是该压栈序列的弹出序列。

解答：代码如下：

bool IsPopOrder(vector<int> pushV,vector<int> popV) { if(pushV.size() == 0 || popV.size() == 0) { return false; } stack<int> sta; int i = 0; int j = 0; while(i < pushV.size()) { sta.push(pushV[i++]); while(j < popV.size() && sta.top() == popV[j]) { sta.pop(); j++; } } return sta.empty(); }

面试题23：从上往下打印二叉树

题目：从上往下打印出二叉树的每个结点，同一层的结点按照从左到右的顺序打印。二叉树结点的定义如下：

struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; };

解答：代码如下：

vector<int> PrintFromTopToBottom(BinaryTreeNode* root) { vector<int> vec; if(NULL == root) { return vec; } deque<BinaryTreeNode *> que; que.push_back(root); while(!que.empty()) { BinaryTreeNode *pNode = que.front(); que.pop_front(); vec.push_back(pNode->m_nValue); if(pNode->m_pLeft != NULL) { que.push_back(pNode->m_pLeft); } if(pNode->m_pRight != NULL) { que.push_back(pNode->m_pRight); } } return vec; }

面试题24：二叉搜索树的后序遍历序列

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true，否则返回false。假设输入的数组的任意两个数字都互不相同。

解答：代码如下：

bool Verify(vector<int> sequence,int left,int right) { if(sequence.empty()|| left > right) { return false; } int root = sequence[right]; int i = left; for(;i < right;i++) { if(sequence[i] > root) { break; } } for(int j = i;j < right;j++) { if(sequence[j] < root) { return false; } } bool Left = true; if(i > left) { Left = Verify(sequence,left,i - 1); } bool Right = true; if(i < right - 1) { Verify(sequence,i,right - 1); } return Left && Right; } bool VerifySquenceOfBST(vector<int> sequence) { if(sequence.size() == 0) { return false; } return Verify(sequence,0,sequence.size() - 1); }

面试题25：二叉树中和为某一值的路径

题目：输入一棵二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的结点形成一条路径。二叉树结点的定义如下：

struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; };

解答：代码如下：

void DFSfind(vector<vector<int>> &res,vector<int> &vec,BinaryTreeNode* root,int expectNumber,int sum) { if(NULL == root) { return ; } vec.push_back(root->m_nValue); sum += root->m_nValue; if(root->m_pLeft == NULL && root->m_pRight == NULL && sum == expectNumber) { res.push_back(vec); sum = 0; } if(root->m_pLeft != NULL) { DFSfind(res,vec,root->m_pLeft,expectNumber,sum); } if(root->m_pRight != NULL) { DFSfind(res,vec,root->m_pRight,expectNumber,sum); } vec.pop_back(); } vector<vector<int>> FindPath(BinaryTreeNode* root,int expectNumber) { vector<vector<int>> res; if(NULL == root) { return res; } vector<int> vec; int sum = 0; DFSfind(res,vec,root,expectNumber,sum); return res; }