建设银行湖南省分行官方网站seo教学网seo

题目

104. 二叉树的最大深度

给定一个二叉树 root ，返回其最大深度。

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

题解

思路：递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def maxDepth(self, root):""":type root: Optional[TreeNode]:rtype: int"""if root is None:return 0else:left_height = self.maxDepth(root.left)right_height = self.maxDepth(root.right)return max(left_height, right_height) + 1

解释

• if root is None:：这行代码首先检查当前节点是否为空（即是否是一个叶子节点或空树）。如果是空节点，则深度为 0。

• left_height = self.maxDepth(root.left)：如果当前节点不是空的，那么递归调用 maxDepth来计算当前节点左子树的深度。

• right_height = self.maxDepth(root.right)：同样的，递归调用 maxDepth 来计算右子树的深度。

• return max(left_height, right_height) + 1：通过 max(left_height, right_height) 计算左右子树深度的最大值，再加 1 表示当前节点的深度。

        1/ \2   3/ \4   5

• 对于根节点 1，我们计算其左子树（节点 2）和右子树（节点 3）的最大深度。

• 左子树的最大深度是 3（节点 2 -> 节点 4 或节点 5），右子树的最大深度是 1（只有节点 3）。

• 所以，最大深度是 max(3, 1) + 1 = 4。