( “树” 之 DFS) 104. 二叉树的最大深度 ——【Leetcode每日一题】

你的名字 2024-03-23 09:58 32阅读 0赞

### 104. 二叉树的最大深度 ###

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

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

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

##### 示例： #####

> 给定二叉树 \[3,9,20,null,null,15,7\]，

![在这里插入图片描述][2f5085666e184ebcb888b083f3b4711e.png]

> 返回它的最大深度 3 。

#### 思路：DFS ####

一棵树要么是**空树**，要么有**两个指针**，每个指针指向一棵树。

*  树是一种**递归**结构，很多树的问题可以使用递归来处理。

#### 代码：(Java、C++) ####

**Java**

/**
     * 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;
            return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
        }
    }

**C++**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
     * };
     */
    class Solution {
        
    public:
        int maxDepth(TreeNode* root) {
        
            if(root == NULL) return 0;
            return 1 + max(maxDepth(root->left), maxDepth(root->right));
        }
    };

##### 运行结果： #####

![在这里插入图片描述][4b17b54b259d4a40b4a08adc9cecbb9b.png]

##### 复杂度分析： #####

*  **时间复杂度**： O ( n ) O(n) O(n)，其中 `n` 为二叉树节点的个数。每个节点在递归中只被遍历一次。
 *  **空间复杂度**： O ( h e i g h t ) O(height) O(height)，其中 `height` 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。

题目来源：[力扣。][Link 1]

> 放弃一件事很容易，每天能坚持一件事一定很酷，一起每日一题吧！  
> 关注我 [leetCode专栏][leetCode]，每日更新！

##### 注： 如有不足，欢迎指正！ #####

[2f5085666e184ebcb888b083f3b4711e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/1e4281a3784145259027650438efe522.png
[4b17b54b259d4a40b4a08adc9cecbb9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/b98eb3b9961347afb6e79a7b8de56fc9.png
[Link 1]: https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?orderBy=most_votes
[leetCode]: http://t.csdn.cn/kQLJO