《剑指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. 假如有一个单独的数字在开头，那么它一定与第二个数字不相等。例如（1/2/2/3/3/4）
2. 假如有一个单独的数字在末尾，那么它一定与倒数第二个数字不相等。例如(1/2/2/3/3/4)
3. 假如有一个数字在中间（从第2位到最后一位），那么它一定与左边和右边的两个数字不相等。例如(1/2/3/3/4/4)或者(1/2/2/3/4/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;
    }