【剑指offer】4.3 具体让抽象问题具体化

面试题21包含min函数的栈题目定义栈的数据结构请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中调用min、push及pop的时间复杂度都是O(1)。解答代码如下stackint ValSta; stackint 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(vectorint pushV,vectorint popV) { if(pushV.size() 0 || popV.size() 0) { return false; } stackint 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; };解答代码如下vectorint PrintFromTopToBottom(BinaryTreeNode* root) { vectorint vec; if(NULL root) { return vec; } dequeBinaryTreeNode * 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(vectorint 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(vectorint 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(vectorvectorint res,vectorint 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(); } vectorvectorint FindPath(BinaryTreeNode* root,int expectNumber) { vectorvectorint res; if(NULL root) { return res; } vectorint vec; int sum 0; DFSfind(res,vec,root,expectNumber,sum); return res; }