力扣 104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
方案一：递归，遍历每一个节点。（自底向上统计信息，分治思想）
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func maxDepth(root *TreeNode) int {
// 如果节点为空直接返回
if root == nil {
return 0
}
// 对比左右节点那个深度更深， +1 是为了加上本层高度
return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
- 时间复杂度：O(n)，n 为树中节点个数，因为需要遍历树中每个节点，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，n 为树中节点个数，树在最好情况下深度为 logn，最差情况下为 n，所以空间复杂度为 O(n)。
方案二：递归，遍历每一个节点。（自顶向下维护信息，在叶子处计算结果）
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var ans int
func maxDepth(root *TreeNode) int {
// 初始化结果
ans = 0
// 从当前节点开始递归
recur(root, 0)
return ans
}
func recur(root *TreeNode, dept int) {
// 当前节点的上一个为叶子结点
if root == nil {
ans = max(ans, dept)
return
}
// 增加层数，往子树递归
dept++
recur(root.Left, dept)
recur(root.Right, dept)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
- 时间复杂度：O(n)，n 为树中节点个数，因为需要遍历树中每个节点，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，n 为树中节点个数，树在最好情况下深度为 logn，最差情况下为 n，所以空间复杂度为 O(n)。