剑指Offer系列（java版，详细解析）55.二叉树的深度
题目一
题目描述
二叉树的深度
输入一颗二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
二叉树的节点定义如下：
测试用例
- 功能测试（输入普通的二叉树；二叉树中所有节点都没有左/右子树）
- 特殊输入测试（二叉树只有一个节点；二叉树的头节点为空指针）
解题思路
递归思路
一个树的深度可以理解为左、右子树深度的最大值加1。
参考解题
/**
* 二叉树的深度
*
*/
public class Solution1 {
/**
* 递归
* @param root
* @return
*/
public int treeDepth(BinaryTreeNode root) {
if (root == null) {
return 0;
}
int left = treeDepth(root.left);
int right = treeDepth(root.right);
return Math.max(left, right) + 1;
}
}
题目二
平衡二叉树
输入一颗二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树任意节点的左、右子树的深度相差不超过1，那么它就是一颗平衡二叉树。
测试用例
- 功能测试（输入普通的二叉树；不是平衡的二叉树；二叉树中所有节点都没有左/右子树）
- 特殊输入测试（二叉树只有一个节点；二叉树的头节点为空指针）
参考解题
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
题目考点
- 考察应聘者对二叉树的理解和编程能力。
- 考察应聘者对新概念（树的深度）的学习能力。
- 考查应聘者的知识迁移能力。