Question

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

二叉树的结点定义如下：

例如，图6.1中的二叉树的深度为4，因为它从根结点到叶结点最长的路径包含4个结点（从根结点1开始，经过结点2和结点5，最终到达叶结点7）。

图6.1　深度为4的二叉树

在本题中面试官给出了一种树的深度的定义，我们可以根据这个定义去得到树的所有路径，也就能得到最长的路径及它的长度。在面试题25二叉树中和为某一值的路径中我们详细讨论了如何记录树中的路径。这种思路的代码量比较大，我们可以尝试更加简洁的方法。

我们还可以从另外一个角度来理解树的深度。如果一棵树只有一个结点，它的深度为1。如果根结点只有左子树而没有右子树，那么树的深度应该是其左子树的深度加1；同样如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1。如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。比如在图6.1的二叉树中，根结点为1的树有左右两个子树，其左右子树的根结点分别为结点2和3。根结点为2的左子树的深度为3，而根结点为3的右子树的深度为2，因此根结点为1的树的深度就是4。

这个思路用递归的方法很容易实现，只需对遍历的代码稍作修改即可。参考代码如下：

源代码：

本题完整的源代码详见39_1_TreeDepth项目。

测试用例：

- 功能测试（输入普通的二叉树，二叉树中所有结点都没有左/右子树）。

- 特殊输入测试（二叉树只有一个结点，二叉树的头结点为NULL指针）。

只要应聘者对二叉树这一数据结构很熟悉，就能很快写出上面的代码。如果公司对编程能力有较高的要求，面试官可能会追加一个与前面问题相关但难度更大的问题。比如，在应聘者做完上面的问题之后，面试官追问：

题目二：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如，图6.1中的二叉树就是一棵平衡二叉树。

需要重复遍历结点多次的解法，简单但不足以打动面试官

有了求二叉树的深度的经验之后再解决这个问题，我们很容易就能想到一个思路：在遍历树的每个结点的时候，调用函数TreeDepth得到它的左右子树的深度。如果每个结点的左右子树的深度相差都不超过1，按照定义它就是一棵平衡的二叉树。这种思路对应的代码如下：

上面的代码固然简洁，但我们也要注意到由于一个结点会被重复遍历多次，这种思路的时间效率不高。例如在函数IsBalance中输入图6.1中的二叉树，我们将首先判断根结点（结点1）是不是平衡的。此时我们往函数TreeDepth输入左子树的根结点（结点2）时，需要遍历结点4、5、7。接下来判断以结点2为根结点的子树是不是平衡树的时候，仍然会遍历结点4、5、7。毫无疑问，重复遍历同一个结点会影响性能。接下来我们寻找不需要重复遍历的算法。

每个结点只遍历一次的解法，正是面试官喜欢的

如果我们用后序遍历的方式遍历二叉树的每一个结点，在遍历到一个结点之前我们就已经遍历了它的左右子树。只要在遍历每个结点的时候记录它的深度（某一结点的深度等于它到叶节点的路径的长度），我们就可以一边遍历一边判断每个结点是不是平衡的。下面是这种思路的参考代码：

我们只需给上面的函数传入二叉树的根结点及一个表示结点深度的整型变量即可：

在上面的代码中，我们用后序遍历的方式遍历整棵二叉树。在遍历某结点的左右子结点之后，我们可以根据它的左右子结点的深度判断它是不是平衡的，并得到当前结点的深度。当最后遍历到树的根结点的时候，也就判断了整棵二叉树是不是平衡二叉树。

源代码：

本题完整的源代码详见39_2_BalancedBinaryTree项目。

测试用例：

- 功能测试（平衡的二叉树，不是平衡的二叉树，二叉树中所有结点都没有左/右子树）。

- 特殊输入测试（二叉树中只有一个结点，二叉树的头结点为NULL指针）。

本题考点：

- 考查对二叉树的理解及编程能力。这两个题的解法实际都只是树的遍历算法的应用。

- 考查对新概念的学习能力。面试官提出一个新的概念即树的深度，这就要求我们在较短的时间内理解这个概念并解决相关的问题。这是一种常见的面试题型。能在较短时间内掌握、理解新概念的能力，就是一种学习能力。

- 考查知识迁移的能力。如果面试官先问如何求二叉树的深度，再问如何判断一棵二叉树是不是平衡的，应聘者应该从求二叉树深度的分析过程中得到启发，找到判断平衡二叉树的突破口。