当前位置：首页 > news >正文

力扣刷题-二叉树-二叉树的高度与深度

news 2025/8/26 5:35:21

二叉树最大深度

给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：3

递归法

本题可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）
而根节点的高度就是二叉树的最大深度，所以本题中我们通过后序求的根节点高度来求的二叉树最大深度。
这一点其实是很多同学没有想清楚的，很多题解同样没有讲清楚。

体现后序遍历的过程！！！使用前序的话要复杂的多
递归第一点：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。
递归第二点：如果为空节点的话，就返回0，表示高度为0。
递归第三点：
**先求它的左子树的深度，再求右子树的深度，最后取左右深度最大的数值再+1 **（加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。（也就是高度）

class solution:def maxdepth(self, root: treenode) -> int:return self.getdepth(root)def getdepth(self, node):if not node:return 0leftdepth = self.getdepth(node.left) # 左rightdepth = self.getdepth(node.right) # 右depth = max(leftdepth, rightdepth) + 1 # 中return depth

精简版：

class solution:def maxdepth(self, root: treenode) -> int:if not root:return 0return 1 + max(self.maxdepth(root.left), self.maxdepth(root.right))

层次遍历

from collections import dequeclass TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightclass Solution(object):def maxDepth(self, root):""":type root: TreeNode:rtype: int"""if not root:return 0result = []queue = deque([root])while queue:level_result = []for _ in range(len(queue)):cur = queue.popleft()level_result.append(cur.val)if cur.left:queue.append(cur.left)if cur.right:queue.append(cur.right)result.append(level_result)return len(result) # 里面多少嵌套列表 即为最大深度