LeetCode，Go实现二叉树的最大深度
力扣题目：
给定一个二叉树，找出其最大深度。 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
解题思路
- 递归 DFS（深度优先搜索 Depth-First-Search） ：
首先，我们要知道一棵树的最大深度在逻辑上怎么求？
- 树的最大深度 = 根节点的高度（根本身为 1 ）+ 左右子树的最大深度中的较大者。
- 左右子树最大深度怎么求呢？以左子树为例，把它看成新的一棵树，那么它的最大深度就是：根节点的高度（根本身为 1 ）+ 左右子树的最大深度中的较大者。
- 这样来思考，就发现递归的所在点了。
- 注意临界点，当树根为空时，说明树不存在，深度为 0。
程序实现：
/**
* 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
}
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(height)，其中 height 表示二叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度。
- 迭代 BFS （广度优先搜索 Breadth-First-Search）：我们也可以用「广度优先搜索」的方法来解决这道题目。我们先将根节点放入队列，然后开始向下遍历，每次拓展下一层的时候，需要将队列里的所有节点都拿出来进行拓展，使队列里存放的是当前层的所有节点，我们用一个变量 ans 来表示拓展的次数，该二叉树的最大深度即为 ans。
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
queue := []*TreeNode{}
queue = append(queue, root)
ans := 0
for len(queue) > 0 {
sz := len(queue)
for sz > 0 {
node := queue[0]
queue = queue[1:]
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
sz--
}
ans++
}
return ans
}
复杂度分析
- 时间复杂度：O(n)，其中 n 为二叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。
- 空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-07-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
