《剑指Offer》题目解析（10）
标签：剑指offer
题目1 二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
题目解析
如果一棵树只有一个结点，那么深度为1.如果根节点只有左子树而没有右子树，那么深度就是左子树深度+1；同理，对于右子树也是如此。如果既有左子树，也有右子树，那么该树的深度就是左右子树深度的最大值+1。所以可以利用递归的方式实现该题目。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
int TreeDepth(TreeNode* pRoot) { int Hl, Hr, MaxH; if(pRoot) { Hl=TreeDepth(pRoot->left); Hr=TreeDepth(pRoot->right); MaxH=(Hl>Hr)?Hl:Hr; return MaxH + 1; } else return 0; } |
题目2 数组中只出现一次的数字
题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
题目解析
这一题我们来对这个数组进行分析。我的想法是首先对其排序，这样这部分复杂度是O(nlogn)，然后我们再来考虑排好序的数组中，这两个特殊的数字会有什么特点呢？
- 假如有一个单独的数字在开头，那么它一定与第二个数字不相等。例如（1/2/2/3/3/4）
- 假如有一个单独的数字在末尾，那么它一定与倒数第二个数字不相等。例如(1/2/2/3/3/4)
- 假如有一个数字在中间（从第2位到最后一位），那么它一定与左边和右边的两个数字不相等。例如(1/2/3/3/4/4)或者(1/2/2/3/4/4)。
- 剩余一个数字肯定也符合上面3种情况中两种情况之一（第一个数字占据了之外的那种情况）。
所以这样，我们就可以把代码写出来了。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) { sort(data.begin(),data.end()); int len=data.size(); vector<int> temp; if(data[0]!=data[1])//第一种情况 temp.push_back(data[0]); for(int i=1;i<len-1;++i)//第二种情况 if(data[i]!=data[i-1] && data[i]!=data[i+1]) temp.push_back(data[i]); if(data[len-1]!=data[len-2])//第三种情况 temp.push_back(data[len-1]); *num1=temp[0]; *num2=temp[1]; } |
题目3 数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
题目解析
借鉴前面数组中只出现一次的数字的思想，同样使用数组，利用hash的思想来做。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
bool duplicate(int numbers[], int length, int* duplication) { if(numbers==NULL||length==0) return 0; int isused[255]={0}; for(int i=0;i<length;i++) { isused[numbers[i]]++; } int count=0; for(int i=0;i<length;i++) { if(isused[numbers[i]]>1) { duplication[count++]=numbers[i]; return true; } } return false; } |
