题解 | #二叉树的最大深度#

秒懂【二叉树最大深度】！超清晰图解一步步拆解。

1.思路

二叉树的最大深度（高度）可以通过递归来实现。对于一个节点来说，最大深度（高度）可以这样计算：左右子树的最大深度（高度）+1（1为当前节点对应的高度）。

先来看看是否满足递归的条件：

可以看出，求解二叉树的最大深度（高度）可以采用递归。对于一个节点来说，最大深度（高度）为：左右子树的最大深度（高度）+1（1为当前节点对应的高度）。因此对应的递推公式如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

2.代码

2.1 Python代码

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型
#
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # write code here
        # 2. 递归终止条件：节点为空，深度为0
        if root is None:
            return 0

        # 1. 问题分解（递推公式）
        # 1.1 获取左子树的深度
        left_max = self.maxDepth(root.left)
        # 1.2 获取右子树的深度
        right_max = self.maxDepth(root.right)
        # 左右子树的最大值
        max_value = max(left_max, right_max)
        # 1.3 返回：左右子树深度的最大值 + 1（当前节点）
        return max_value + 1

2.2 Java代码

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        // write code here
        // 2. 递归终止条件：节点为空，深度为0
        if (root == null) {
            return 0;
        }

        // 1. 问题分解（递推公式）
        // 1.1 获取左子树的深度
        int leftMax = maxDepth(root.left);
        // 1.2 获取右子树的深度
        int rightMax = maxDepth(root.right);
        // 左右子树的最大值
        int maxValue = Math.max(leftMax, rightMax);
        // 1.3 返回：左右子树深度的最大值+1（当前节点）
        return maxValue + 1;
    }
}

2.3 Go代码

**如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解**：[B站@好易学数据结构](https://space.bilibili.com/408058258)package main

import . "nc_tools"
import (
	
	"math"
	
)

/*
 * type TreeNode struct {
 *   Val int
 *   Left *TreeNode
 *   Right *TreeNode
 * }
 */

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param root TreeNode类
 * @return int整型
 */
func maxDepth(root *TreeNode) int {
	// write code here

	// 2. 递归终止条件：节点为空，深度为0
	if root == nil {
		return 0
	}

	// 1. 问题分解（递推公式）
	// 1.1 获取左子树的深度
	leftMax := maxDepth(root.Left)
	// 1.2 获取右子树的深度
	rightMax := maxDepth(root.Right)
	// 左右子树的最大值
	maxValue := int(math.Max(float64(leftMax), float64(rightMax)))
	// 1.3 返回：左右子树深度的最大值+1（当前节点）
	return maxValue + 1
}

如果上面的代码理解的不是很清楚，你可以参考视频的详细讲解：B站@好易学数据结构