【LeetCode】22.Maximum depth of binary tree· 二叉树的最大深度

电玩女神 2024-04-03 07:48 19阅读 0赞

## 题目描述 ##

### 英文版描述 ###

Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

### 英文版地址 ###

https://leetcode.com/problems/maximum-depth-of-binary-tree/

### 中文版描述 ###

给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

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

/ \\

9 20

/ \\

15 7

返回它的最大深度 3

### 中文版地址 ###

https://leetcode.cn/problems/maximum-depth-of-binary-tree/

## 解题思路 ##

设置一个变量maxValue，用于存储该树的最大深度，遍历求每一个节点的深度并与maxValue进行比较，大于maxValue则替换，小于或等于则保持不变

## 解题方法 ##

### 俺这版 ###

![c87d856d6ba2d128461ce3b830264f7e.png][]

/**
     * 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 {
        int maxValue = 0;
    
        public int maxDepth(TreeNode root) {
            // 设置一个变量maxValue，用于存储该树的最大深度，遍历求每一个节点的深度并与maxValue进行比较，大于maxValue则替换，小于或等于则保持不变
            getDeepth(root);
            return maxValue;
        }
    
        public int getDeepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int deepthLeft = getDeepth(root.left);
            int deepthRight = getDeepth(root.right);
            int newVaule = Math.max(deepthLeft, deepthRight) + 1;
            maxValue = Math.max(maxValue, newVaule);
            return newVaule;
        }
    }

**复杂度分析**

*  时间复杂度：O(n)，n为树的节点个数
 *  空间复杂度：O(Height)，Height为树深度

### 官方版 ###

#### 方法一：深度优先搜索 ####

这个跟我上面的解法基本一致，就不重复描述了

#### 方法二：广度优先搜索 ####

![d296f9e4a2a6e5ef5ae18a30d662c6d2.png][]

**思路与算法**

我们也可以用「广度优先搜索」的方法来解决这道题目，但我们需要对其进行一些修改，此时我们广度优先搜索的队列里存放的是「当前层的所有节点」。每次拓展下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行拓展，这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行拓展，最后我们用一个变量 ans 来维护拓展的次数，该二叉树的最大深度即为ans

/**
     * 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;
            }
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            int ans = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                while (size > 0) {
                    TreeNode node = queue.poll();
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                    size--;
                }
                ans++;
            }
            return ans;
        }
    }

**复杂度分析**

*  时间复杂度：O(n)，其中 n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。
 *  空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。

[c87d856d6ba2d128461ce3b830264f7e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/acee1e07d5fa4a779926ab9ece34f081.png
[d296f9e4a2a6e5ef5ae18a30d662c6d2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/03/bd3b20e779934a75a713066216b4dbe8.png

【LeetCode】22.Maximum depth of binary tree· 二叉树的最大深度

发表评论取消回复

还没有评论，来说两句吧...

相关阅读