题目1 二叉树的深度

题目描述

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

题目解析

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

代码

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

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

代码

题目3 数组中重复的数字

题目描述

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

题目解析

借鉴前面数组中只出现一次的数字的思想,同样使用数组,利用hash的思想来做。

代码