Leecode热题100---104：二叉树的最大深度(广度/深度优先)

题目：
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

解题思路：
树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）。

常见 DFS ： 先序遍历、中序遍历、后序遍历。
常见 BFS ： 层序遍历（即按层遍历）。
求树的深度需要遍历树的所有节点，本文将介绍基于 后序遍历（DFS） 和 层序遍历（BFS） 的两种解法。

C++：
1、后序遍历(DFS)
关键点： 此树的深度和其左（右）子树的深度之间的关系。显然，此树的深度 等于 左子树的深度 与 右子树的深度中的 最大值 +1。

算法解析：

1. 终止条件： 当 root​ 为空，说明已越过叶节点，因此返回 深度 000 。
2. 递推工作： 本质上是对树做后序遍历。
   2.1 计算节点 root​ 的 左子树的深度 ，即调用 maxDepth(root.left)。
   2.2 计算节点 root​ 的 右子树的深度 ，即调用 maxDepth(root.right)。
3. 返回值： 返回 此树的深度 ，即 max(maxDepth(root.left), maxDepth(root.right)) + 1。

#include<iostream>
#include<algorithm>

using namespace std;

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode()
	{
		int x = 0;
	}
	TreeNode(int x)
	{
		val = x;
		left = right = nullptr;
	}
	TreeNode(int x, TreeNode *left, TreeNode *right)
	{
		val = x;
		left = left;
		right = right;
	}
};
// 后序遍历
// 关键点：树的深度 == 左子树的深度 与 右子树的深度中的 最大值 +1
class Solution
{
public:
	int maxDepth(TreeNode* root)
	{
		if (root == nullptr) return 0;
		return max(maxDepth(root->left), maxDepth(root->right)) + 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
33
34
35
36
37

2、层序遍历（BFS）
关键点： 每遍历一层，则计数器 +1+1+1 ，直到遍历完成，则可得到树的深度。

算法解析：

1. 特例处理： 当 root​ 为空，直接返回 深度 000 。
2. 初始化： 队列 queue （加入根节点 root ），计数器 res = 0。
3. 循环遍历： 当 queue 为空时跳出。
   a. 初始化一个空列表 tmp ，用于临时存储下一层节点。
   b. 遍历队列： 遍历 queue 中的各节点 node ，并将其左子节点和右子节点加入 tmp。
   c. 更新队列： 执行 queue = tmp ，将下一层节点赋值给 queue。
   d. 统计层数： 执行 res += 1 ，代表层数加 1。
4. 返回值： 返回 res 即可。

#include<iostream>
#include<algorithm>

using namespace std;

struct TreeNode
{
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode()
	{
		int x = 0;
	}
	TreeNode(int x)
	{
		val = x;
		left = right = nullptr;
	}
	TreeNode(int x, TreeNode *left, TreeNode *right)
	{
		val = x;
		left = left;
		right = right;
	}
};


// 层序遍历
//关键点： 每遍历一层，则计数器 + 1 ，直到遍历完成，则可得到树的深度。

#include<vector>
class Solution1
{
public:
	int maxDepth(TreeNode* root)
	{
		if (root == nullptr) return 0;
		vector<TreeNode*> que;  // 容器：用于存储下一层的节点，类型为链表中的节点，故为<TreeNode*>
		que.push_back(root);
		int res = 0;
		while (! que.empty())  // 队列que为空时跳出
		{
			vector<TreeNode*>tmp; // 临时列表，用于存储当前层的打印结果
			for (TreeNode* node : que)
			{
				// 添加下一层的子节点至tmp，用于下一步计算
				if (node->left != nullptr) tmp.push_back(node->left);
				if (node->right != nullptr) tmp.push_back(node->right);
			}
			que = tmp;
			res++;
		}
		return res;
	}
};
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

python:

1、后序遍历/深度优先（DFS）
思路同上：

class TreeNode:
    def __init__(self,val = 0,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxDepth(self,root):
        if not root: return 0
        return max(self.maxDepth(root.left),self.maxDepth(root.right)) + 1
1
2
3
4
5
6
7
8
9
10

2、层序遍历/广度优先（BFS）

class TreeNode:
    def __init__(self,val = 0,left=None,right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def maxDepth(self,root):
        if not root: return 0
        queue, res = [root], 0
        while queue:
            tmp=[]
            for node in queue:
                if node.left: tmp.append(node.left)
                if node.right: tmp.append(node.right)
            queue = tmp
            res += 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18