二叉树的深度 - JZ38
题目描述
输入一棵二叉树的根节点，求该树的深度。
从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
数据范围： 节点数量满足 0 ≤ n ≤ 100，节点上的值满足 0 ≤ val ≤ 100
示例：
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回它的最大深度 3。
解题思路
这是一道经典的递归问题，有多种解法：
-
递归法（深度优先搜索）：
- 树的深度 = max(左子树深度, 右子树深度) + 1
- 递归终止条件：空节点深度为0
-
迭代法（广度优先搜索）：
- 使用队列层序遍历，计算层数
- 每处理完一层，深度+1
项目结构
.
├── go.mod # Go 模块定义
├── types.go # 二叉树类型定义和工具函数
├── solution.go # 算法实现（你需要完成这个文件）
├── answer.go # 参考答案（练习后查看）
├── solution_test.go # 单元测试
└── README.md # 说明文档
使用方法
1. 实现算法
在 solution.go 文件中实现：
maxDepth(root *TreeNode) int- 主要实现maxDepthIterative(root *TreeNode) int- 迭代实现
2. 运行测试
go test -v
go test -bench=.
时间和空间复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 递归法 | O(n) | O(h) | h是树的高度，递归调用栈 |
| 迭代法 | O(n) | O(w) | w是树的最大宽度 |
知识点
- 二叉树的遍历
- 递归思想
- 深度优先搜索(DFS)
- 广度优先搜索(BFS)
- 树的高度vs深度的概念