LeetCode算法系列（Java版） 104. 二叉树的最大深度
LeetCode算法系列（Java版） 111. 二叉树的最小深度
力扣原题
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
解题思路
-
树的总深度 = max(左子树深度，右子树深度) + 当前节点所在的一层深度； -
左子树深度 = max(左子树的左子树深度，左子树的右子树深度) + 当前节点所在的一层深度； -
右子树深度 = max(右子树的左子树深度，右子树的右子树深度) + 当前节点所在的一层深度； -
递归，直到节点为 null；
代码实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
} else {
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}
}
复杂度分析
-
时间复杂度：，其中 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。
-
空间复杂度：此方法空间的消耗取决于二叉树的元素数量，其在最坏情况下会达到 。
LeetCode算法系列（Java版） 104. 二叉树的最大深度
LeetCode算法系列（Java版） 111. 二叉树的最小深度
原文始发于微信公众号（白菜说技术）：LeetCode算法系列 104. 二叉树的最大深度
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/172713.html
