104. 二叉树的最大深度【75】

向右看齐 2023-09-26 22:19 91阅读 0赞

> **难度等级：容易**

> **上一篇算法：**
> 
> [ 101. 对称二叉树【74】][101. _74]

> **力扣此题地址：**
> 
> [104. 二叉树的最大深度 - 力扣（Leetcode）][104. _ - _Leetcode]

## 1.题目：104. 二叉树的最大深度 ##

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

**说明:** 叶子节点是指没有子节点的节点。

![42ada1c5a8ba44b589beebedf9ba1a71.png][]

## 2.解题思路： ##

> **深度优先：**
> 
> 一棵树的深度 = max（左子树的深度，右子树的深度）+1
> 
> 也就是左子树和右子树的深度取最大的，再加1，就等于当前结点的深度。
> 
> 那么，根据这个思想，我们可以用递归的方式，分别递归左子树和右子树，依次递归下去，就得到了树的深度。
> 
> **代码思路：**
> 
> （1）先判断树是否为null，为null返回0
> 
> （2）树不为null的话，分别递归左子树、右子树，
> 
> 最终return max（左子树的深度，右子树的深度）+1

## 3.代码实现： ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        public int maxDepth(TreeNode root) {
            if(root == null){
                return 0;
            }else{
                int leftHeight = maxDepth(root.left);
                int rightHeight = maxDepth(root.right);
                return Math.max(leftHeight,rightHeight)+1;
            }
        }
    }

> **深度优先搜索：**深度优先搜索会**沿着一条路径不断往下搜索**直到不能再继续为止，然后再折返，开始搜索下一条路径。
> 
> **广度优先搜索：**广度优先搜索会根据离起点的距离，按照**从近到远的顺序对各节点进行搜索。**

[101. _74]: https://blog.csdn.net/m0_51697147/article/details/130302296?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22130302296%22%2C%22source%22%3A%22m0_51697147%22%7D
[104. _ - _Leetcode]: https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/
[42ada1c5a8ba44b589beebedf9ba1a71.png]: https://img-blog.csdnimg.cn/42ada1c5a8ba44b589beebedf9ba1a71.png