剑指 Offer 55 - I. 二叉树的深度 - leetcode 剑指offer系列题目难度:简单原题链接[1]今天

题目难度: 简单
原题链接[1]
今天继续更新剑指 offer 系列, 老样子晚上 6 点 45 分准时更新公众号每日精选算法题, 大家记得关注哦~ 另外在公众号里回复 offer 就能看到剑指 offer 系列当前连载的所有文章了
题目描述输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

节点总数 <= 10000

题目样例示例【剑指 Offer 55 - I. 二叉树的深度 - leetcode 剑指offer系列】给定二叉树 [3,9,20,null,null,15,7] ，3/ \920/\157返回它的最大深度 3。 题目思考

如果限制只能用递归或者迭代, 如何解决?

解决方案方案 1思路

先考虑递归做法, 尝试 DFS
我们可以这样构造递归方法: 传入节点, 返回当前节点的深度, 该深度是左右子树的最大深度+1
假设叶子节点的深度为 1, 显然根节点的深度就是整个树的最大深度了
递归出口即节点为空的情况, 此时深度为 0

复杂度

时间复杂度 O(N): 需要遍历整个树
空间复杂度 O(H): H 表示树的高度, 也即递归的栈的消耗

代码

class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:# 递归出口, 空节点的情况return 0# 当前节点深度是左右子树的最大深度+1return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))# 也可以进一步简化为只需要一行代码..# return 0 if not root else 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

方案 2思路

如果要求必须用迭代方式实现, 那方案 1 就不行了
迭代一般可以先尝试 BFS, 这道题也不例外
通过分析题目, 显然这里的深度就是指 BFS 的层数, 所以完全可以利用剑指 Offer 32 - II. 从上到下打印二叉树 II - leetcode 剑指 offer 系列的做法得出层数, 只是不需要打印出每一层的节点, 只需要统计层数即可. 不清楚的同学可以先看看那道题的思路~
下面代码对必要的步骤有详细的解释, 方便大家理解

复杂度

时间复杂度 O(N): 需要遍历整个树
空间复杂度 O(N): 队列的空间消耗

代码

class Solution:def maxDepth(self, root: TreeNode) -> int:if not root:return 0q = [root]res = 0while q:# 当前层节点数目curlen = len(q)for node in q[:curlen]:# 只追加非空子节点if node.left:q.append(node.left)if node.right:q.append(node.right)# 队列切片, 开始处理下一层q = q[curlen:]# 当前层遍历完毕, 深度+1res += 1return res

参考资料[1]
原题链接: