看完了书，准备把书中的代码全部手敲一遍，正好九度上有《剑指Offer》的专题，于是就在上面做了。（虽然个人更喜欢leetcode）。原题不贴，只贴代码及简单解释。部分题目仅从Oj的角度看是没什么意思的，必须按照题目的要求来解才有意义。虽然平时项目用的代码多是java，但a题还是喜欢用C/C++。
题目1384：二维数组中的查找
两种思路：书上的思路是从右上或者左下开始搜索，一次排除一行或一列。另一种思路是逐行排除，因为是有序的，因此可以用二分。下面是两种思路的代码：
#include <cstdio>
using namespace std;
const int MAX=1000;
int matrix[MAX][MAX];
bool findNumber(int m,int n,int t)
{
bool sign=0;
if (m>0&&n>0&&matrix!=NULL)
{
int row = 0,column = n-1;
while (row<m&&column>=0)
{
if (t==matrix[row][column])
{
sign = true;
break;
}else if (t>matrix[row][column])
{
row++;
}else
{
column--;
}
}
}
return sign;
}
int main()
{
int m(0),n(0),t(0);
while(scanf("%d %d",&m,&n)!=EOF)
{
scanf("%d",&t);
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
scanf("%d",&matrix[i][j]);
}
}
if(findNumber(m,n,t))
printf("Yes\n");
else
printf("No\n");
}
}#include <cstdio>
using namespace std;
const int MAX=1000;
int matrix[MAX][MAX];
int main()
{
int m(0),n(0),t(0);
while(scanf("%d %d",&m,&n)!=EOF)
{
scanf("%d",&t);
int size(n-1);
for(int i=0;i<m;++i)
{
for(int j=0;j<n;++j)
{
scanf("%d",&matrix[i][j]);
}
}
int sign=0;
for(int i=0;0==sign && i<m;++i)
{
if(t<matrix[i][0])
{
sign=0;
break;
}
else if(t>matrix[i][size])
{
continue;
}
else
{
int low(0),high(size);
while(low<=high)
{
int mid=(low+high)/2;
if(matrix[i][mid]==t)
{
sign=1;
break;
}
else if(matrix[i][mid]<t)
{
low=mid+1;
}
else
{
high=mid-1;
}
}
}
}
if(sign)
printf("Yes\n");
else
printf("No\n");
}
}思路是从后往前替换，代码如下：
#include <stdio.h>
#include <string.h>
int main(void){
char str[1000001];
int len;
int new_len;
int i;
int cnt;
gets (str);
len = strlen (str);
cnt = 0;
for (i=0; i<len; ++i){
if (str[i] == ‘ ‘)
++cnt;
}
new_len = len + 2 * cnt;
str[new_len] = ‘\0‘;
--len;
--new_len;
while (len >= 0&&new_len>len){
if (str[len] != ‘ ‘){
str[new_len] = str[len];
--new_len;
}
else{
str[new_len--] = ‘0‘;
str[new_len--] = ‘2‘;
str[new_len--] = ‘%‘;
}
--len;
}
puts (str);
return 0;
}这个没什么好说的，用栈，代码如下：
#include <cstdio>
#include <stack>
using namespace std;
const int MAX=10000;
int main()
{
int number;
std::stack<int> stackNumber;
while(scanf("%d",&number)!=EOF&&number!=-1)
{
stackNumber.push(number);
}
while (!stackNumber.empty()) {
printf("%d\n",stackNumber.top());
stackNumber.pop();
}
return 0;
}根据前序遍历和中序遍历的特点先构建出此二叉树来，再输出其后序遍历序列。代码如下：
#include <cstdio>
#include <stack>
using namespace std;
bool findTree = false;
typedef struct Node
{
int value;
Node * left;
Node * right;
Node(int value)
{
this->value = value;
left = right = NULL;
}
}TreeNode;
TreeNode* RebuildTree(int *startPreOrder,int *endPreOrder,int *startMidOrdre,int *endMidOrdre){
int rootPreeValue =startPreOrder[0];
TreeNode* root=new Node(rootPreeValue);
if (startPreOrder==endPreOrder) {
if (startMidOrdre==endMidOrdre&&*startPreOrder==*startMidOrdre) {
return root;
}else{
findTree = false;
return root;
}
}
int *midRoot = startMidOrdre;
while (midRoot<endMidOrdre&&*midRoot!=rootPreeValue) {
midRoot++;
}
if (midRoot==endMidOrdre&&*midRoot!=rootPreeValue) {
findTree = false;
return root;
}
long leftLength = midRoot - startMidOrdre;
if (leftLength>0) {
root->left =RebuildTree(startPreOrder+1,startPreOrder+leftLength,startMidOrdre,midRoot-1);
}
if (endPreOrder-startPreOrder-leftLength>0) {
root->right =RebuildTree(startPreOrder+leftLength+1,endPreOrder,midRoot+1,endMidOrdre);
}
return root;
}
void printTree(TreeNode* tree){
if (tree==NULL) {
return;
}
if (tree->left!=NULL) {
printTree(tree->left);
}
if (tree->right!=NULL) {
printTree(tree->right);
}
printf("%d ",tree->value);
}
int main()
{
int number;
int preOrder[1000],midOrder[1000];
while(scanf("%d",&number)!=EOF)
{
if (number<=0) {
printf("No\n");
}
for (int i=0; i<number; i++) {
scanf("%d",&preOrder[i]);
}
for (int i=0; i<number; i++) {
scanf("%d",&midOrder[i]);
}
findTree = true;
TreeNode* tree =RebuildTree(preOrder,preOrder+number-1,midOrder,midOrder+number-1);
if (findTree) {
printTree(tree);
printf("\n");
}else{
printf("No\n");
}
}
return 0;
}栈1存储新插入的，栈2负责输出，栈2为空时，把栈1的数据倒过去。代码如下：
#include <cstdio>
#include <stack>
#include <vector>
#include <iostream>
using namespace std;
stack<int> st1,st2;
void pop(){
if (st2.size()<=0) {
while (!st1.empty()) {
int value = st1.top();
st1.pop();
st2.push(value);
}
}
if (st2.empty()) {
printf("-1\n");
}else{
printf("%d\n",st2.top());
st2.pop();
}
}
void push(int val){
st1.push(val);
}
int main()
{
int m,n;
char operStr[15];
scanf("%d",&m);
for (int i=0; i<m; i++) {
scanf("%s",operStr);
if (operStr[1]==‘U‘) {
scanf("%d",&n);
push(n);
}else{
pop();
}
}
return 0;
}二分查找的灵活应用，注意特殊情况，代码如下：
#include <cstdio>
#include <stack>
#include <vector>
#include <iostream>
using namespace std;
int MinInorder(int *data,int index1,int index2){
int result=data[index1];
for (index1+=1; index1<=index2; index1++) {
if (result>data[index1]) {
result = data[index1];
}
}
return result;
}
int Min(int data[],int index1,int index2){
int midIndex = index1;
while (data[index1]>=data[index2]) {
if (index2-index1==1) {
midIndex=index2;
break;
}
midIndex = (index2+index1)/2;
if (data[index2]==data[index1]&&data[index2]==data[midIndex]) {
return MinInorder(data,index1,index2);
}
if (data[index1]<=data[midIndex]) {
index1=midIndex;
}else if (data[index2]>=data[midIndex]){
index2 = midIndex;
}
}
return data[midIndex];
}
int main()
{
int m;
while (scanf("%d",&m)!=EOF) {
int data[m];
for (int i=0; i<m; i++) {
scanf("%d",&data[i]);
}
if (m>0) {
printf("%d\n",Min(data,0,m-1));
}
}
return 0;
}别用递归就行，代码如下：
#include <cstdio>
#include <string>
using namespace std;
long long getFBNQ(int n){
if (n==0) {
return 0;
}else if(n==1){
return 1;
}
long long number1(0),number2(1),result;
long long index=2;
while (index++<=n) {
result = number1 + number2;
number1 = number2;
number2 = result;
}
return result;
}
int main()
{
int num;
while (scanf("%d",&num)!=EOF) {
printf("%lld\n",getFBNQ(num));
}
return 0;
}找完规律后，发现这道题最简单了，代码如下：
#include <cstdio>
#include <math.h>
using namespace std;
long long getFBNQ(int n){
if (n>0) {
return pow(2,n-1);
}else{
return 0;
}
// if (n==1) {
// return 1;
// }else if(n==2){
// return 2;
// }
// long long data[50],result;
// data[0]=1,data[1]=2;
// long long index=2;
// while (index<n) {
// result=0;
// for (int i=0; i<index; i++) {
// result+=data[i];
// }
// data[index]=result+1;
// index++;
// }
// return result+1;
}
int main()
{
int num;
while (scanf("%d",&num)!=EOF) {
printf("%lld\n",getFBNQ(num));
}
return 0;
}利用一个数与这个数减1后的数相与，去掉最后一个1的特性，代码如下：
#include <cstdio>
#include <math.h>
using namespace std;
char numberOf1(int number){
char count=0;
while (number) {
count++;
number=number&(number-1);
}
return count;
}
int main()
{
int num,data;
scanf("%d",&num);
for (int i=0; i<num; i++) {
scanf("%d",&data);
printf("%d\n",numberOf1(data));
}
return 0;
}注意次数为负的情况及浮点等于的判断，代码如下：
#include <cstdio>
using namespace std;
double pow(double base,int exponent){
if (exponent==0) {
return 1;
}else if(exponent==1){
return base;
}
double result=pow( base, exponent>>1);
result *= result;
if (exponent&1) {
result*=base;
}
return result;
}
bool equle0(double base){
if (base<0.0000001&&base>-0.0000001) {
return true;
}
return false;
}
void powOfDouble(double base,int exponent){
if (equle0(base)) {
if (exponent<0) {
printf("INF\n");
}else{
printf("%.2ef\n",0.0);
}
return ;
}
double result = pow(base,exponent>0?exponent:-exponent);
printf("%.2ef\n",exponent>0?result:1.0/result);
}
int main()
{
int num,exponent;
double base;
scanf("%d",&num);
for (int i=0; i<num; i++) {
scanf("%lf %d",&base,&exponent);
powOfDouble(base,exponent);
}
return 0;
}这个要求比书中降低了，代码如下：
#include <cstdio>
#include <math.h>
//#include <iostream.h>
using namespace std;
int main()
{
int num,data;
scanf("%d",&num);
data=pow(10,num);
for (int i=1; i<data; i++) {
printf("%d\n",i);
//cout<<i<<endl;
}
return 0;
}偶数和偶数之间的相对位置不变比较麻烦，最后只能增加了O(n)的空间，以空间换取时间，代码如下：
#include <cstdio>
using namespace std;
int main()
{
int num,countOfOdd=0;
scanf("%d",&num);
int data[num],data1[num];
for (int i=0; i<num; i++) {
scanf("%d",&data[i]);
if (data[i]&1) {
countOfOdd ++ ;
}
}
int index=0;
for (int i=0; i<num; i++){
if (data[i]&1){
data1[index++]=data[i];
}else{
data1[countOfOdd++]=data[i];
}
}
printf("%d",data1[0]);
for (int i=1; i<num; i++){
printf(" %d",data1[i]);
}
return 0;
}用前后两个指针，注意边界判断，代码如下：
#include <cstdio>
using namespace std;
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
int main()
{
int n,k,val;
Node *head;
while (scanf("%d%d",&n,&k)!=EOF) {
scanf("%d",&val);
head = new Node(val);
Node *node = head;
for (int i=1; i<n; i++) {
scanf("%d",&val);
Node *nodeNew = new Node(val);
node->next=nodeNew;
node = nodeNew;
}
if (k>n||k<=0) {
printf("NULL\n");
continue;
}else{
node = head;
for (int i=0; i<k-1; i++) {
node = node->next;
}
while (node->next!=NULL) {
node = node->next;
head = head->next;
}
printf("%d\n",head->val);
}
}
return 0;
}题目1518：反转链表
两种思路，一种是重新起一个链表，每遍历一个结点，将此结点插到前面结点的前面，另一种方法是修改链表的指针指向，实现反转，下面的代码实现的是前者：
#include <cstdio>
//#include <iostream.h>
using namespace std;
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
void revertList(Node **head){
Node *pHead = (*head)->next;
Node *nextNode;
(*head)->next=NULL;
while (pHead!=NULL) {
nextNode=pHead->next;
pHead->next = *head;
*head = pHead;
pHead = nextNode;
}
}
int main()
{
int n,val;
while (scanf("%d",&n)!=EOF) {
if (n==0) {
printf("NULL\n");
continue;
}
scanf("%d",&val);
Node *head = new Node(val);
Node *node=head;
for (int i=1; i<n; i++) {
scanf("%d",&val);
Node *tmpNode = new Node(val);
node->next=tmpNode;
node=tmpNode;
}
revertList(&head);
node = head;
if (node!=NULL) {
printf("%d",node->val);
node=node->next;
}
while (node!=NULL) {
printf(" %d",node->val);
node=node->next;
}
printf("\n");
}
return 0;
}题目1519：合并两个排序的链表
思路当然是比较每个链表的最前面元素，注意为NULL的情况，可用递归，也可用循环，代码如下：
递归：
#include <cstdio>
//#include <iostream.h>
using namespace std;
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
Node* Merge(Node* pHead1, Node* pHead2)
{
if(pHead1 == NULL)
return pHead2;
else if(pHead2 == NULL)
return pHead1;
Node* pMergedHead = NULL;
if(pHead1->val < pHead2->val)
{
pMergedHead = pHead1;
pMergedHead->next = Merge(pHead1->next, pHead2);
}
else
{
pMergedHead = pHead2;
pMergedHead->next = Merge(pHead1, pHead2->next);
}
return pMergedHead;
}
int main()
{
int m,n,val;
while (scanf("%d%d",&m,&n)!=EOF) {
if (n<=0&&m<=0) {
printf("NULL\n");
continue;
}
Node *head1=NULL, *head2=NULL,*node=NULL;
if (m>0)
{
scanf("%d",&val);
head1 = new Node(val);
node=head1;
for (int i=1; i<m; i++) {
scanf("%d",&val);
Node *tmpNode = new Node(val);
node->next=tmpNode;
node=tmpNode;
}
}
if (n>0)
{
scanf("%d",&val);
head2 = new Node(val);
node=head2;
for (int i=1; i<n; i++) {
scanf("%d",&val);
Node *tmpNode = new Node(val);
node->next=tmpNode;
node=tmpNode;
}
}
node = Merge(head1,head2);
if (node!=NULL) {
printf("%d",node->val);
node=node->next;
}
while (node!=NULL) {
printf(" %d",node->val);
node=node->next;
}
printf("\n");
}
return 0;
}#include <cstdio>
//#include <iostream.h>
using namespace std;
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
void MergeLortList(Node **head,Node *head1,Node *head2){
if (head1==NULL)
{
*head = head2;
return;
}else if (head2==NULL)
{
*head = head1;
return;
}
Node *p1=head1,*p2=head2,*p3;
if (p1->val<=p2->val)
{
*head=p1;
p1=p1->next;
}else
{
*head=p2;
p2=p2->next;
}
p3=*head;
while (p1!=NULL&&p2!=NULL) {
if (p1->val<=p2->val)
{
p3->next=p1;
p3=p1;
p1=p1->next;
}else
{
p3->next=p2;
p3=p2;
p2=p2->next;
}
}
if (p1==NULL)
{
p3->next=p2;
}else
{
p3->next=p1;
}
}
int main()
{
int m,n,val;
while (scanf("%d%d",&m,&n)!=EOF) {
if (n<=0&&m<=0) {
printf("NULL\n");
continue;
}
Node *head1=NULL, *head2=NULL,*node=NULL;
if (m>0)
{
scanf("%d",&val);
head1 = new Node(val);
node=head1;
for (int i=1; i<m; i++) {
scanf("%d",&val);
Node *tmpNode = new Node(val);
node->next=tmpNode;
node=tmpNode;
}
}
if (n>0)
{
scanf("%d",&val);
head2 = new Node(val);
node=head2;
for (int i=1; i<n; i++) {
scanf("%d",&val);
Node *tmpNode = new Node(val);
node->next=tmpNode;
node=tmpNode;
}
}
Node *head;
MergeLortList(&head,head1,head2);
node = head;
if (node!=NULL) {
printf("%d",node->val);
node=node->next;
}
while (node!=NULL) {
printf(" %d",node->val);
node=node->next;
}
printf("\n");
}
return 0;
}题目1520：树的子结构
前序遍历，递归判断，代码如下：
#include <cstdio>
//#include <iostream.h>
using namespace std;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
void setValue(int val){
this->m_nValue=val;
m_pLeft=m_pRight=NULL;
}
};
void constructTree(int m,BinaryTreeNode tree[]){
int val,childIndex;
if (m>0)
{
for(int i=0;i<m;i++){
scanf("%d",&val);
tree[i].setValue(val);
}
for(int i=0;i<m;i++){
scanf("%d",&val);
if (val>=1)
{
scanf("%d",&childIndex);
tree[i].m_pLeft=&tree[childIndex-1];
if (val==2)
{
scanf("%d",&childIndex);
tree[i].m_pRight=&tree[childIndex-1];
}
}
}
}
}
bool HasSubtreeCore(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2);
bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2);
bool HasSubtree(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
bool result = false;
if(pRoot1 != NULL && pRoot2 != NULL)
{
if(pRoot1->m_nValue == pRoot2->m_nValue)
result = DoesTree1HaveTree2(pRoot1, pRoot2);
if(!result)
result = HasSubtree(pRoot1->m_pLeft, pRoot2);
if(!result)
result = HasSubtree(pRoot1->m_pRight, pRoot2);
}
return result;
}
bool DoesTree1HaveTree2(BinaryTreeNode* pRoot1, BinaryTreeNode* pRoot2)
{
if(pRoot2 == NULL)
return true;
if(pRoot1 == NULL)
return false;
if(pRoot1->m_nValue != pRoot2->m_nValue)
return false;
return DoesTree1HaveTree2(pRoot1->m_pLeft, pRoot2->m_pLeft) &&
DoesTree1HaveTree2(pRoot1->m_pRight, pRoot2->m_pRight);
}
int main()
{
int m,n,val,childIndex;
BinaryTreeNode tree1[1000], tree2[1000];
while (scanf("%d%d",&m,&n)!=EOF) {
constructTree(m,tree1);
constructTree(n,tree2);
if (n<=0||m<=0) {
printf("NO\n");
continue;
}
if(HasSubtree(tree1, tree2))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}题目1521：二叉树的镜像找规律，前序遍历，分别交换左右结点即可，代码如下：
#include <cstdio>
//#include <iostream.h>
using namespace std;
int treeNodeNumbers;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
void setValue(int val){
this->m_nValue=val;
m_pLeft=m_pRight=NULL;
}
};
void constructTree(int m,BinaryTreeNode tree[]){
int val,childIndex;
if (m>0)
{
for(int i=0;i<m;i++){
scanf("%d",&val);
tree[i].setValue(val);
}
for(int i=0;i<m;i++){
scanf("\n%c",&val);
if (val==‘d‘||val==‘l‘||val==‘r‘)
{
scanf("%d",&childIndex);
if (val==‘l‘||val==‘d‘)
{
tree[i].m_pLeft=&tree[childIndex-1];
if (val==‘d‘)
{
scanf("%d",&childIndex);
tree[i].m_pRight=&tree[childIndex-1];
}
}else
{
tree[i].m_pRight=&tree[childIndex-1];
}
}
}
}
}
void MirrorIteratively(BinaryTreeNode* pRoot)
{
if(pRoot == NULL||(pRoot->m_pLeft==NULL&&pRoot->m_pRight==NULL))
return;
BinaryTreeNode* pTmpTree;
pTmpTree = pRoot->m_pLeft;
pRoot->m_pLeft = pRoot->m_pRight;
pRoot->m_pRight = pTmpTree;
if (pRoot->m_pLeft!=NULL)
{
MirrorIteratively(pRoot->m_pLeft);
}
if (pRoot->m_pRight!=NULL)
{
MirrorIteratively(pRoot->m_pRight);
}
}
void PrintTree(BinaryTreeNode* pRoot)
{
if(pRoot == NULL)
return;
if (treeNodeNumbers-->1)
printf("%d ",pRoot->m_nValue);
else
printf("%d",pRoot->m_nValue);
if (pRoot->m_pLeft!=NULL)
PrintTree(pRoot->m_pLeft);
if (pRoot->m_pRight!=NULL)
PrintTree(pRoot->m_pRight);
}
int main()
{
int m,n,val,childIndex;
BinaryTreeNode tree[1000];
while (scanf("%d",&m)!=EOF) {
if (m<=0)
{
printf("NULL\n");
continue;
}
constructTree(m,tree);
MirrorIteratively(tree);
treeNodeNumbers = m;
PrintTree(tree);
}
return 0;
}题目1391：顺时针打印矩阵
各种情况的考虑，代码如下：
#include <cstdio>
//#include <iostream.h>
using namespace std;
void printValue(int val);
int numbers[1000][1000];
void PrintMatrixInCircle( int columns, int rows){
if(numbers == NULL || columns <= 0 || rows <= 0)
return;
int start=0;
while (columns > start * 2 && rows > start * 2)
{
int endX = columns - 1 - start;
int endY = rows - 1 - start;
//从左到右打印
for(int i = start; i <= endX; ++i)
{
printValue(numbers[start][i]);
}
//从上到下
if(start < endY)
{
for(int i = start + 1; i <= endY; ++i)
{
printValue(numbers[i][endX]);
}
}
//从右到左
if(start < endX && start < endY)
{
for(int i = endX - 1; i >= start; --i)
{
printValue(numbers[endY][i]);
}
}
// 从下到上
if(start < endX && start < endY - 1)
{
for(int i = endY - 1; i >= start + 1; --i)
{
printValue(numbers[i][start]);
}
}
++start;
}
}
void printValue(int val){
printf("%d ",val);
}
int main()
{
int m,n;
while (scanf("%d%d",&m,&n)!=EOF) {
for(int i=0;i<m;i++){
for (int j = 0; j < n; j++)
{
scanf("%d",&numbers[i][j]);
}
}
PrintMatrixInCircle(n,m);
printf("\n");
}
return 0;
}题目1522：包含min函数的栈
使用一个辅助栈，记录当前的min，代码如下：
#include <cstdio>
#include <stack>
using namespace std;
void printValue(int val){
printf("%d\n",val);
}
void printMinInstack(int m){
int val;
stack<int> st,stMin;
char c;
for(int i=0;i<m;i++){
scanf("\n%c",&c);
if (c==‘s‘)
{
scanf("%d",&val);
if (!stMin.empty()&&val>stMin.top()) {
stMin.push(stMin.top());
}else{
stMin.push(val);
}
st.push(val);
printValue(stMin.top());
}else{
if (stMin.empty()) {
printf("NULL\n");
}else{
stMin.pop();
st.pop();
if (!stMin.empty()){
printValue(stMin.top());
}else{
printf("NULL\n");
}
}
}
}
}
int main()
{
int m;
while (scanf("%d",&m)!=EOF) {
printMinInstack(m);
}
return 0;
}题目1366：栈的压入、弹出序列
判断压入序列的当前操作数据是否等于当前出栈数据，是则弹出，否则继续压入，如果所有数据都压入了，出栈序列还有数据，则不是正确的弹出序列，代码如下：
#include <cstdio>
#include <stack>
using namespace std;
bool isPopList(const int *pushList,const int *popList,const int n){
bool sign = true;
stack<int> pushSt;
int pushIndex=0,popIndex=0;
while (popIndex<n) {
if (!pushSt.empty()) {
if (pushSt.top()==popList[popIndex]) {
pushSt.pop();
popIndex++;
}else if(pushIndex<n){
pushSt.push(pushList[pushIndex++]);
}else{
sign = false;
break;
}
}else if(pushIndex<n){
pushSt.push(pushList[pushIndex++]);
}else{
sign = false;
break;
}
}
return sign;
}
int main()
{
int n;
while (scanf("%d",&n)!=EOF&&n>0) {
int list1[n],list2[n];
for (int i=0; i<n; i++) {
scanf("%d",&list1[i]);
}
for (int i=0; i<n; i++) {
scanf("%d",&list2[i]);
}
if(isPopList(list1,list2,n)){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
题目1523：从上往下打印二叉树
使用队列，代码如下：
#include <cstdio>
#include <queue>
using namespace std;
int treeNodeNumbers;
struct BinaryTreeNode
{
int m_nValue;
BinaryTreeNode* m_pLeft;
BinaryTreeNode* m_pRight;
void setValue(int val){
this->m_nValue=val;
m_pLeft=m_pRight=NULL;
}
};
void constructTree(int m,BinaryTreeNode tree[]){
int val,childIndex;
char c;
if (m>0)
{
for(int i=0;i<m;i++){
scanf("%d",&val);
tree[i].setValue(val);
}
for(int i=0;i<m;i++){
scanf("\n%c",&c);
if (c==‘d‘||c==‘l‘||c==‘r‘)
{
scanf("%d",&childIndex);
if (c==‘l‘||c==‘d‘)
{
tree[i].m_pLeft=&tree[childIndex-1];
if (c==‘d‘)
{
scanf("%d",&childIndex);
tree[i].m_pRight=&tree[childIndex-1];
}
}else
{
tree[i].m_pRight=&tree[childIndex-1];
}
}
}
}
}
void PrintValue(int val){
if ((treeNodeNumbers--)>1)
printf("%d ",val);
else
printf("%d",val);
}
void PrintTree(BinaryTreeNode* pRoot)
{
if(pRoot == NULL)
return;
BinaryTreeNode* pHead = pRoot;
queue<BinaryTreeNode*> q;
q.push(pHead);
while (q.size()) {
PrintValue(q.front()->m_nValue);
pHead=q.front();
q.pop();
if (pHead->m_pLeft!=NULL) {
q.push(pHead->m_pLeft);
}
if (pHead->m_pRight!=NULL) {
q.push(pHead->m_pRight);
}
}
}
int main()
{
int m;
BinaryTreeNode tree[1000];
while (scanf("%d",&m)!=EOF) {
constructTree(m,tree);
treeNodeNumbers = m;
PrintTree(tree);
}
return 0;
}题目1367：二叉搜索树的后序遍历序列
后序遍历最后一个是根，根前面的小于根，后面的大于根，根据这个特点，使用递归，可以写出代码如下：
#include <cstdio>
using namespace std;
bool isSortTree(const int* data,int length ){
if (data==NULL||length<=0) {
return false;
}
int root = data[length-1];
int i=0;
//找到开始大于根结点的位置
for (; i<length-1; i++) {
if (data[i]>root) {
break;
}
}
for (int j=i; j<length-1; j++) {
if (data[j]<root) {
return false;
}
}
bool left=true;
if (i>0) {
left=isSortTree(data, i);
}
bool right=true;
if (length-1>i) {
right=isSortTree(data+i, length-i-1);
}
return left&&right;
}
int main()
{
int m;
int tree[10000];
while (scanf("%d",&m)!=EOF) {
for (int i=0; i<m; i++) {
scanf("%d",&tree[i]);
}
if (isSortTree(tree,m)) {
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}题目1368：二叉树中和为某一值的路径
前序遍历，遍历的时候分别记录当前的和及路径，如果是叶子结点则判断是否等于要找的和，否则减去此结点的值，从路径中删除，继续下一个结点，代码如下：
#include <iostream>
#include <vector>
using namespace std;
typedef struct {
int val;
int left;
int right;
} node;
void find(const vector<node> &vec, const int &target, int idx,vector<int> &path,int &cnt) {
const node &cur = vec[idx];
//如果当前已经是叶子结点，且找到了和，则打印路径
if (cnt + cur.val == target && cur.left == -2 && cur.right == -2) {
cout << "A path is found:";
for (vector<int>::const_iterator iter = path.begin();
iter != path.end(); ++iter) {
cout << " " << *iter + 1;
}
cout << " " << idx + 1 << endl;
} else {
cnt += cur.val;
path.push_back(idx);
//确保字典顺序
if (cur.left != -2 && cur.right != -2) {
if (cur.left < cur.right) {
find(vec, target, cur.left,path,cnt);
find(vec, target, cur.right,path,cnt);
} else {
find(vec, target, cur.right,path,cnt);
find(vec, target, cur.left,path,cnt);
}
}else if (cur.left != -2) {
find(vec, target, cur.left,path,cnt);
}else if (cur.right != -2){
find(vec, target, cur.right,path,cnt);
}
// this node is done
path.pop_back();
cnt -= cur.val;
}
}
int main(void) {
int cnt;
int target, i;
node n;
vector<int> path;
while (cin >> cnt) {
vector<node> vec;
cin >> target;
for (i = 0; i < cnt; ++i) {
cin >> n.val >> n.left >> n.right;
--n.left;
--n.right;
vec.push_back(n);
}
cout << "result:" << endl;
path.clear();
int currentSum = 0;
find(vec, target, 0,path,currentSum);
}
}
【九度-剑指Offer题目笔记】上,布布扣,bubuko.com
原文：http://blog.csdn.net/viviwen123/article/details/21930843