《剑指Offer》题目解析（10）

题目1 二叉树的深度

题目描述

输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

题目解析

如果一棵树只有一个结点，那么深度为1.如果根节点只有左子树而没有右子树，那么深度就是左子树深度+1；同理，对于右子树也是如此。如果既有左子树，也有右子树，那么该树的深度就是左右子树深度的最大值+1。所以可以利用递归的方式实现该题目。

代码

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种情况中两种情况之一（第一个数字占据了之外的那种情况）。

所以这样，我们就可以把代码写出来了。

代码

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的思想来做。

代码

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;
}