剑指offer（六）

26. 顺时针打印矩阵

因为弄反了行列，所以因为溢出折腾了好一会。做之前感觉递归会更方便，现在还是觉得循环更简单些。

class Solution { public: void printM(vector<vector<int> > matrix,int rowbegin,int rowend,int colbegin,int colend,vector<int>& result){ if(rowbegin>rowend || colbegin>colend) return; int i=colbegin,j=rowbegin; if(rowbegin==rowend){ while(i<=colend) {result.push_back(matrix[i][j]);i++;} return; } else if(colbegin==colend){ while(j<=rowend) {result.push_back(matrix[i][j]);j++;} return; } while(j<rowend) {result.push_back(matrix[i][j]);j++;} while(i<colend) {result.push_back(matrix[i][j]);i++;} while(j>rowbegin) {result.push_back(matrix[i][j]);j--;} while(i>colbegin) {result.push_back(matrix[i][j]);i--;} if(rowbegin<rowend && colbegin<colend) printM(matrix,rowbegin+1,rowend-1,colbegin+1,colend-1,result); return; } vector<int> printMatrix(vector<vector<int> > matrix) { vector<int> result; if(matrix.size()==0) return result; if(matrix[0].size()==0) return result; int rowend=matrix[0].size()-1; int colend=matrix.size()-1; int rowbegin=0,colbegin=0; if(rowbegin<=rowend && colbegin<=colend) printM(matrix,rowbegin,rowend,colbegin,colend,result); return result; } };

27. 包含min函数的栈

class Solution { public: stack<int> stack1,stack2; void push(int value) { stack1.push(value); if(stack2.empty()) stack2.push(value); else{ if(value<=stack2.top()) stack2.push(value); } } void pop() { if(stack1.top()==stack2.top()) stack2.pop(); stack1.pop(); } int top() { return stack1.top(); } int min() { return stack2.top(); } };

28. 栈的压入、弹出序列

建立辅助栈，模拟栈的压入弹出过程看是否能全弹出.

class Solution { public: bool IsPopOrder(vector<int> pushV,vector<int> popV) { if(pushV.size()==0 || popV.size()==0) return false; stack<int> stk; int i=0; for(int j=0;j<pushV.size() && i<popV.size();j++){ stk.push(pushV[j]); while(i<popV.size() && !stk.empty() && stk.top()==popV[i]){ stk.pop(); i++; } } if(stk.empty()) return true; return false; } };

29. 打印二叉树

29.1 从上到下打印二叉树

使用队列，先进先出，按顺序保留每个子节点。

class Solution { public: vector<int> PrintFromTopToBottom(TreeNode* root) { vector<int> print; if(root==NULL) return print; queue<TreeNode*> que; que.push(root); while(!que.empty()){ root=que.front(); que.pop(); if(root==NULL) continue; print.push_back(root->val); que.push(root->left); que.push(root->right); } return print; } };

29.2. 分行从上到下打印二叉树

使用一个int值计数，记下一层节点个数countnext，当前节点个数count会在遍历完当前层之后重新赋值为countnext，开始遍历下一层。

class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> result; vector<int> col; if(pRoot==NULL) return result; queue<TreeNode*> que; que.push(pRoot); int count=1,countnext=0; while(!que.empty()){ pRoot=que.front(); if(pRoot->left!=NULL){ que.push(pRoot->left); countnext++; } if(pRoot->right!=NULL){ que.push(pRoot->right); countnext++; } que.pop(); col.push_back(pRoot->val); count--; if(count==0){ result.push_back(col); col.clear(); count=countnext; countnext=0; } } return result; } };

29.3 之字形打印二叉树

class Solution { public: vector<vector<int> > Print(TreeNode* pRoot) { vector<vector<int>> result; vector<int> col; if(pRoot==NULL) return result; stack<TreeNode*> stknext; stack<TreeNode*> stk; stk.push(pRoot); bool ceng=true;//分奇偶层； int count=1,countnext=0; while(!stk.empty()){ pRoot=stk.top(); //收集下一层的节点 if(pRoot->left!=NULL && ceng){ stknext.push(pRoot->left); countnext++; } if(pRoot->right!=NULL){ stknext.push(pRoot->right); countnext++; } if(pRoot->left!=NULL && !ceng){ stknext.push(pRoot->left); countnext++; } stk.pop(); col.push_back(pRoot->val); count--; if(count==0){ //捋一下下一层节点的顺序 result.push_back(col); col.clear(); count=countnext; countnext=0; ceng=!ceng; stk=stknext; //因为没有能直接清空栈的方法，用了一个笨方法。 stack<TreeNode*> empt; stknext=empt; } } return result; } };

30. 二叉搜索树的后序遍历序列

class Solution { public: bool VerifySquenceOfBST(vector<int> sequence) { //搜索树默认中序遍历有序，所以相当于找中序与后序的联系 int size=sequence.size(); if(size==0) return false; if(size==1) return true; vector<int> left; vector<int> right; int i=0; bool leftflag=true; while(i<size-1){ //左子树 if(sequence[i]<sequence[size-1] && leftflag){ left.push_back(sequence[i]); i++; } //右子树 else if(sequence[i]>sequence[size-1]){ leftflag=false; right.push_back(sequence[i]); i++; } //应该在右子树的但小于根节点，异常 else return false; } //最初输入的树为空应 false；这里为了区别最初的空还是后来的空。 bool leftBST=left.size()<=1? true :VerifySquenceOfBST(left); bool rightBST=right.size()<=1? true :VerifySquenceOfBST(right); return leftBST && rightBST; } };