图解LeetCode——剑指 Offer 55 - I. 二叉树的深度

一、题目

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

二、示例

2.1> 示例1：

【输入】给定二叉树 [3,9,20,null,null,15,7]，

【输出】返回它的最大深度 3 。

提示：

• 节点总数 <= 10000

三、解题思路

• 根据题目描述，我们要计算出这棵二叉树的深度，那么我们可以通过深度遍历或者广度遍历这两种遍历方式，来获得这道题的最终解。
• 下面我们采用深度遍历的方式来解题，由于二叉树的深度是需要根据左子树深度和右子树深度进行对比后取最大值才能计算出来，所以我们采用深度遍历中的后序遍历方式，即：先遍历左子树，然后遍历右子树，最后遍历子树的根节点。那么它的代码模型是这样的：

publicvoiddfs(TreeNodenode) {
    ... ...
dfs(root.left); // 遍历左子树dfs(root.right); // 遍历右子树node// 遍历根节点    ... ...    
}

• 所以，当我们遍历到某个叶子节点之后，我们返回深度depth等于0，然后每次向上层返回的时候，都执行加1操作。那么当返回到根节点之后，就是某一侧分支的深度了。其中，在每次向上返回一层都执行加1时，我们应该主要，对于每层来说，这个节点在理论上应该是具有左子树和右子树的，所以我们需要先通过Math.max(左子树深度， 右子树深度)，来确定最深的子树，然后再对其执行深度加1的操作。
• 好了，具体解题思路说完了，下面我们以输入=[3,9,20,null,null,15,7]这个二叉树，来计算其二叉树的深度为例，看一下具体的计算过程。请见下图所示：

四、代码实现

classSolution {
publicintmaxDepth(TreeNoderoot) {
if (root==null) return0;
intlDepth=maxDepth(root.left);
intrDepth=maxDepth(root.right);
returnMath.max(lDepth+1, rDepth+1);
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」