二叉树最大深度
二叉树的最大深度
1、题目
![图1](https://2hang.oss-cn-beijing.aliyuncs.com/img/202403302342744.png)
2、题解
树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS)
- 常见DFS:先序遍历、中序遍历、后序遍历
- 常见BFS:层序遍历
后序遍历(递归)
树的深度等于左子树深度和右子树深度最大值加1
算法流程:
终止:当root为空,表明越过叶节点,返回深度0
递归:计算root的左子树深度,即调用\(函数(root.left)\);计算root的右子树深度,即调用\(函数(root.right)\)
返回:返回节点树的深度,即\(max(函数(root.left),函数(root.right))+1\)
1 |
|
层序遍历(队列)
每遍历一层,深度加1,直至遍历完成
算法流程:
- 当root为空,返回深度0
- 初始化队列que(加入根节点),深度res=0
- 遍历:当que为空时结束。
- 初始化一个空列表tmp,用于临时存储下一层的节点。
- 遍历que中的各节点,将其左右子节点加入tmp
- 令que=tmp
- 深度加1
- 返回res
1 |
|
二叉树最大深度
http://example.com/2024/03/30/二叉树最大深度/