二叉树的最大深度 Posted on 2021-06-16 00:00:00 2021-06-26 00:00:00 by Author 摘要 给定一颗二叉树，你能实现一个算法找出该二叉树的最大深度吗？？？？ # 二叉树的最大深度 1. 题目描述 - 给定一个二叉树，找出其最大深度。 - 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 - 叶子节点是指没有子节点的节点。 2. 示例描述 - 示例一 - 输入：[1,2,2,3,4,4,3,5,null,null,6,6,null,null,5]  - 输出：4 - 示例二 - 输入：[1,2,2,3,4,4,3]  - 输出：3 - 示例三 - 输入：[1,null,2,null,null,3,null]  - 输出：3 3. 解题思路 - 这道题实现起来比较简单，主要是理解递归的含义，理解了递归的含义，那么这道题就算一道简单题目，否则的话，实现起来比较难。 - 首先我们确定，如果所给的节点不为空，那么就循环递归寻找该层左孩子与右孩子最大深度，知道找到叶子节点后，然后在回溯到当前节点，就能找到该层下左孩子与右孩子最大的深度，又因为本层节点算一层，所以需要加一，那么每一层递归寻找左右孩子最大深度也同样加一，所以递归的入口处，找到最大深度后需要总体加一。到此整个算法实现完毕。虽然实现起来比较简单，但是要理解递归出口和入口还是有点难度的，需要自己慢慢细品。以下是代码实现,虽然代码只有几行，但是还是需要自己慢慢手动实现一下递归的过程，这样才能更好的理解代码。 4. 代码示例 ```java public int maxDepth(TreeNode root) { //如果正在访问的节点为空，那么本节点深度为0，直接返回为0 if (root == null) { return 0; } //否则本节点不为空，及比较本节点下左孩子与右孩子最大深度 //为什么要加1，因为本层节点算一层，这个递归是寻找本层节点的下一层节点的深度、所以要加一 return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } ```
{{ item.content }}
{{ child.content }}