网站建设公司为什么没有官网,dw在线编辑器,大学学风建设网站,godaddy 安装wordpress二叉树的最大深度 题目题解解释 题目
104. 二叉树的最大深度
给定一个二叉树 root #xff0c;返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
题解
思路#xff1a;递归
# Definition for a binary tree node.
# class TreeN… 二叉树的最大深度 题目题解解释 题目
104. 二叉树的最大深度
给定一个二叉树 root 返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
题解
思路递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right right
class Solution(object):def maxDepth(self, root)::type root: Optional[TreeNode]:rtype: intif 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。
