文章目录
- 前言
- 题目
- 代码实现:
前言
这道题目是力扣上面的一道简单题目,求二叉树的最大深度,我觉得掌握求树的深度问题还是很有必要的,对于AVL等树来说,求树的深度是很重要的问题。
题目
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3 / \ 9 20 / \ 15 7
结果显然易见,为3。
怎么求得树的最大深度呢?
思路:
找出终止条件:当前节点为空
找出返回值:节点为空时说明高度为 0,所以返回0;
节点不为空时则分别求左右子树的高度的最大值,同时加1表示当前节点的高度,返回该数值
意思就是递归处理,比较树的左右子树的高度,返回较高的那棵树的深度。
3 / \ 9 20 / \ 15 7
解析:
比如上面那颗树:root = 3;h(root) = max( h ( root.left ), h ( root.right ) )+1;
h(root.left) = 1 ,因为其的左右结点都为null
h(root.right) = max(h(root.right.left),h(root.right.right))+1;
很明显:h(root.right) = max(1,1)+1 = 2;
所以:h(root) =max(1,2)+1 = 3;
代码实现:
public class MaxDepth {
public int maxDepth(TreeNode root) {
if (root==null){
return 0;
}
return Math.max(root.left==null?0:maxDepth(root.left),root.right==null?0:maxDepth(root.right))+1;
}
}