【算法题解】33. 二叉树的最大深度

系统管理员 2024-03-16 12:07 41阅读 0赞

> 这是一道 **简单** 题  
>   
> https://leetcode.cn/problems/maximum-depth-of-binary-tree/

### 题目 ###

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

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

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

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

3
       / \
      9  20
        /  \
       15   7

返回它的最大深度 `3` 。

### 题解 ###

先取 **左子树的最大深度** 和 **右子树的最大深度** 中的 **最大值**，然后 **加一** 就是二叉树的最大深度。

求子树的最大深度，需要一层一层往下走，每层的算法都相同，典型的递归思路。

**递归函数**：二叉树的最大深度 =  M a x Max Max(左子树的最大深度, 右子树的最大深度) + `1`。  
  
**边界条件**：为空时返回深度为`0`。

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

##### Go 代码实现 #####

/**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func maxDepth(root *TreeNode) int {
    
        if root == nil {
            return 0
        }
    
        return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
        
    }
    
    func max(a, b int) int {
        if a > b {
            return a
        }
        return b
    }

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

*  **时间复杂度**： O ( n ) O(n) O(n), `n` 为二叉树中的节点个数，每个节点计算一次，时间复杂度为 O ( 1 ) O(1) O(1)，`n` 个节点总计为  O ( n ) O(n) O(n)。
 *  **空间复杂度**： O ( n ) O(n) O(n), `n` 为二叉树中的节点个数，空间复杂度为调用栈的深度，最多为 `n`，即二叉树退化为链表的时候。