本文共 1843 字,大约阅读时间需要 6 分钟。
【思路】
树的遍历方式总体分为两类:深度优先搜索(DFS)、广度优先搜索(BFS);
求树的深度需要遍历树的所有节点,本文将介绍基于 后序遍历(DFS) 和 层序遍历(BFS) 的两种解法。
【方法一:后序遍历(DFS)】
树的后序遍历 / 深度优先搜索往往利用 递归 或 栈 实现,本文使用递归实现。算法解析:
图解
依次递归节点 1、7、2,得到深度1、1、2 最后得到树的深度为3 复杂度分析:# 法一:DFS深度优先搜索class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
【方法二:层序遍历(BFS)】
树的层序遍历 / 广度优先搜索往往利用 队列 实现。算法解析:
# 法二:BFS广度优先搜索class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 queue = [root] layer = 0 while queue: # 各节点 tmp = [] for node in queue: if node.left: # 有左,就添加到tmp tmp.append(node.left) if node.right: # 有右,就添加到tmp tmp.append(node.right) queue = tmp layer+=1 return layer
链接:https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/solution/mian-shi-ti-55-i-er-cha-shu-de-shen-du-xian-xu-bia/
转载地址:http://tyjii.baihongyu.com/