剑指Offer面试题39（Java版）：二叉树的深度

秒速五厘米 2022-07-16 04:51 163阅读 0赞

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

例如，如下图的二叉树的深度为４，因为它从根节点到叶结点的最长的路径包含４个结点（从根结点１开始，经过２和结点５，最终到达叶结点７）

![Center][]

我们可以从另一种角度来理解树的深度。如果一棵树只有一个结点，它的深度为1，如果根节点只有左子树而没有右子树，那么树的深度应该是其左子树的深度+1.同样如果根节点只有右子树而没有左子树，那么树的深度应该是其右子树+1.如果既有左子树又有右子树，那概述的深度就是左、右子树的深度的较大值加1.。

利用这个思路，我们可以用递归来实现代码：

**\[java\]**  [view plain][]   [copy][view plain]

1.  //普通二叉树求深度  
2.      **public** **int** treeDepth(BinaryTreeNode root)\{  
3.          **if**(root == **null**)  
4.              **return** 0;  
5.          **int** nLeft = treeDepth(root.leftNode);  
6.          **int** nRight = treeDepth(root.rightNode);  
7.          **return** (nLeft > nRight)?(nLeft+1):(nRight+1);  
8.      \}

如果公司对编程能力有较高的要求，面试官可能会追加一个与前面的问题相关但难度较大的问题，比如，应聘者做完上面的问题后，面试官追问：

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

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

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

**\[java\]**  [view plain][]   [copy][view plain]

1.  //判断是否是一颗平衡二叉树  
2.      **public** **boolean** isBalanced(BinaryTreeNode root)\{  
3.          **if**(root ==**null**)  
4.              **return** **true**;  
5.          **int** left = treeDepth(root.leftNode);  
6.          **int** right = treeDepth(root.rightNode);  
7.          **int** diff = left - right;  
8.          **if**(diff > 1 || diff <-1)  
9.              **return** **false**;  
10.         **return** isBalanced(root.leftNode) && isBalanced(root.rightNode);  
11.     \}

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

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

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

**\[java\]**  [view plain][]   [copy][view plain]

1.  //高效率的判断是否是一棵平衡二叉树  
2.      **public** **boolean** isBalanced2(BinaryTreeNode root)\{  
3.          **int** depth = 0;  
4.          **return** isBalanced2(root,depth);  
5.      \}  
6.      **public** **boolean** isBalanced2(BinaryTreeNode root,**int** depth)\{  
7.          **if**(root == **null**)\{  
8.              depth = 0;  
9.              **return** **true**;  
10.         \}  
11.         **int** left = 0,right = 0;  
12.         **if**(isBalanced2(root.leftNode,left) && isBalanced2(root.rightNode,right))\{  
13.             **int** diff = left-right;  
14.             **if**(diff <= 1 && diff >= -1)\{  
15.                 depth = 1\+(left > right?left : right);  
16.                 **return** **true**;  
17.             \}  
18.         \}  
19.         **return** **false**;  
20.     \}

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

[Center]: /images/20220716/9c510bbae79646cdaba507d2678aa28e.png
[view plain]: http://blog.csdn.net/jsqfengbao/article/details/47393151#