高频算法面试题（三十五）- 二叉树的最大深度

发表于

「这是我参与11月更文挑战的第 20 天，活动详情查看：2021最后一次更文挑战」

刷算法题，从来不是为了记题，而是练习把实际的问题抽象成具体的数据结构或算法模型，然后利用对应的数据结构或算法模型来进行解题。个人觉得，带着这种思维刷题，不仅能解决面试问题，也能更多的学会在日常工作中思考，如何将实际的场景抽象成相应的算法模型，从而提高代码的质量和性能

二叉树的最大深度

题目来源：LeetCode-104.二叉树的最大深度

题目描述

给定一个二叉树，找出其最大深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

说明: 叶子节点是指没有子节点的节点

示例

示例 1

给定二叉树 [3,9,20,null,null,15,7]

1
2
3
4
5
markdown复制代码		3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3

解题

如果你看过我前边的一篇求二叉树的右视图的文章，这道题的思路跟那个差不多，但这个更加的简单

解法一：深度优先搜索

思路

求最大深度，我们最容易想到的其实就是层序遍历。但是你会发现用层序遍历，并不容易记录当前是哪一层。因此，我们可以考虑用深度优先搜索

深度优先搜索：随意选择一个岔路口来走，走着走着发现走不通的时候，就回退到上一个岔路口，重新选择一条路继续走，直到走完所有的情况

假设我们知道了一棵二叉树的左右子树的深度分别是l和r，那么这颗二叉树的最大深度就是max(l, r)+1

而左右子树的最大深度，可以使用相同的方法来计算，那现在递归公式就有了

1
scss复制代码max(maxDepth(root.Left), maxDepth(root.Right))

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
go复制代码func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}

	return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

func max(x, y int) int {
	if x > y {
		return x
	}

	return y
}

解法二：广度优先搜索

思路

广度优先搜索：是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索

广度优先搜索可以借助队列来实现，但是解本题的时候，需要做些变化

  • 队列里边存的是当前层的所有结点
  • 每次遍历下一层的时候，不同于广度优先搜索的每次只从队列里拿出一个节点，我们需要将队列里的所有节点都拿出来进行遍历，这样能保证每次拓展完的时候队列里存放的是当前层的所有节点，即我们是一层一层地进行遍历
  • 每向下遍历一层，深度就+1

代码一看就明白

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
go复制代码//广度优先搜索实现
func maxDepth2(root *TreeNode) int {
	if root == nil {
		return 0
	}

	widthQueue := []*TreeNode{root}
	depth := 0

	for len(widthQueue) != 0 {
		count := len(widthQueue)
		for count > 0 {
			node := widthQueue[0]
			if len(widthQueue) > 1 {
				widthQueue = widthQueue[1:]
			} else {
				widthQueue = []*TreeNode{}
			}
			if node.Left != nil {
				widthQueue = append(widthQueue, node.Left)
			}
			if node.Right != nil {
				widthQueue = append(widthQueue, node.Right)
			}

			count--
		}
		depth++
	}

	return depth
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%