本文共 1843 字，大约阅读时间需要 6 分钟。

一、找树的最大深度

1. 思路一 DFS查找

递归查找左、右子树，查找到叶结点便开始返回，每返回一层，深度加1(逆向理解。正向则可理解为”最大深度+1“，默认从0层开始)；每个子树返回包含最大深度的叶结点

代码

class Solution:    def maxDepth(self, root: TreeNode) -> int:        if not root: return 0                return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

2.思路二 BFS查找

逐层扫描，每扫描完一层，深度便加1

代码

class Solution:    def maxDepth(self, root: TreeNode) -> int:        if not root: return 0                queue = collections.deque()        queue.append(root)        depth = 0                while queue:            level_size = len(queue)                        for _ in range(level_size):                node = queue.popleft()                if node.left: queue.append(node.left)                if node.right: queue.append(node.right)                        depth += 1                return depth

二、找树的最小深度

1.思路一 DFS查找

递归查找到叶结点便开始返回，如果树只有一个子树，则返回该子树的最小深度；否者取左、右子树中最小值深度；return时加1不能忘！

代码

class Solution:    def minDepth(self, root: TreeNode) -> int:        if not root: return 0                left_depth = self.minDepth(root.left)        right_depth = self.minDepth(root.right)                return (left_depth + right_depth + 1) if (not left_depth or not right_depth) else 1 + min(left_depth, right_depth)

2.思路二 BFS查找

找第一个叶结点便返回：第一个叶结点的所在层便是树的最小深度

class Solution:    def minDepth(self, root: TreeNode) -> int:        if not root: return 0                queue = collections.deque()        queue.append(root)        depth = 0                while queue:            level_size = len(queue)            depth += 1                        for _ in range(level_size):                node = queue.popleft()                if not node.left and not node.right:                    return depth                if node.left: queue.append(node.left)                if node.right: queue.append(node.right)

总结

以上方案基本每个结点都会访问一次，所以时间复杂度为O(N)

转载地址：http://hghrb.baihongyu.com/