0104. 二叉树的最大深度

题目地址(104. 二叉树的最大深度)

题目描述

1
给定一个二叉树,找出其最大深度。
2
3
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
4
5
说明: 叶子节点是指没有子节点的节点。
6
7
示例:
8
给定二叉树 [3,9,20,null,null,15,7],
9
10
3
11
/ \
12
9 20
13
/ \
14
15 7
15
返回它的最大深度 3 。
Copied!

前置知识

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节
  • apple
  • linkedin
  • uber
  • yahoo

思路

由于树是一种递归的数据结构,因此用递归去解决的时候往往非常容易,这道题恰巧也是如此,
  • 用递归实现的代码如下:
1
var maxDepth = function (root) {
2
if (!root) return 0;
3
if (!root.left && !root.right) return 1;
4
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
5
};
Copied!
如果使用迭代呢? 我们首先应该想到的是树的各种遍历,由于我们求的是深度,因此 使用层次遍历(BFS)是非常合适的。 我们只需要记录有多少层即可。相关思路请查看binary-tree-traversal

关键点解析

  • 队列
  • 队列中用 Null(一个特殊元素)来划分每层,或者在对每层进行迭代之前保存当前队列元素的个数(即当前层所含元素个数)
  • 树的基本操作- 遍历 - 层次遍历(BFS)

代码

  • 语言支持:JS,C++,Java,Python, Go, PHP
JS Code:
1
/*
2
* @lc app=leetcode id=104 lang=javascript
3
*
4
* [104] Maximum Depth of Binary Tree
5
*/
6
/**
7
* Definition for a binary tree node.
8
* function TreeNode(val) {
9
* this.val = val;
10
* this.left = this.right = null;
11
* }
12
*/
13
/**
14
* @param {TreeNode} root
15
* @return {number}
16
*/
17
var maxDepth = function (root) {
18
if (!root) return 0;
19
if (!root.left && !root.right) return 1;
20
21
// 层次遍历 BFS
22
let cur = root;
23
const queue = [root, null];
24
let depth = 1;
25
26
while ((cur = queue.shift()) !== undefined) {
27
if (cur === null) {
28
// 注意⚠️: 不处理会无限循环,进而堆栈溢出
29
if (queue.length === 0) return depth;
30
depth++;
31
queue.push(null);
32
continue;
33
}
34
const l = cur.left;
35
const r = cur.right;
36
37
if (l) queue.push(l);
38
if (r) queue.push(r);
39
}
40
41
return depth;
42
};
Copied!
C++ Code:
1
/**
2
* Definition for a binary tree node.
3
* struct TreeNode {
4
* int val;
5
* TreeNode *left;
6
* TreeNode *right;
7
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8
* };
9
*/
10
class Solution {
11
public:
12
int maxDepth(TreeNode* root) {
13
if (root == nullptr) return 0;
14
auto q = vector<TreeNode*>();
15
auto d = 0;
16
q.push_back(root);
17
while (!q.empty())
18
{
19
++d;
20
auto sz = q.size();
21
for (auto i = 0; i < sz; ++i)
22
{
23
auto t = q.front();
24
q.erase(q.begin());
25
if (t->left != nullptr) q.push_back(t->left);
26
if (t->right != nullptr) q.push_back(t->right);
27
}
28
}
29
return d;
30
}
31
};
Copied!
Java Code:
1
/**
2
* Definition for a binary tree node.
3
* public class TreeNode {
4
* int val;
5
* TreeNode left;
6
* TreeNode right;
7
* TreeNode(int x) { val = x; }
8
* }
9
*/
10
class Solution {
11
public int maxDepth(TreeNode root) {
12
if(root == null)
13
{
14
return 0;
15
}
16
// 队列
17
Queue<TreeNode> queue = new LinkedList<TreeNode>();
18
queue.offer(root);
19
int res = 0;
20
// 按层扩展
21
while(!queue.isEmpty())
22
{
23
// 拿出该层所有节点,并压入子节点
24
int size = queue.size();
25
while(size > 0)
26
{
27
TreeNode node = queue.poll();
28
29
if(node.left != null)
30
{
31
queue.offer(node.left);
32
}
33
if(node.right != null)
34
{
35
queue.offer(node.right);
36
}
37
size-=1;
38
}
39
// 统计层数
40
res +=1;
41
}
42
return res;
43
}
44
}
Copied!
Python Code:
1
class Solution:
2
def maxDepth(self, root: TreeNode) -> int:
3
if not root: return 0
4
q, depth = [root, None], 1
5
while q:
6
node = q.pop(0)
7
if node:
8
if node.left: q.append(node.left)
9
if node.right: q.append(node.right)
10
elif q:
11
q.append(None)
12
depth += 1
13
return depth
Copied!
Go Code:
1
/**
2
* Definition for a binary tree node.
3
* type TreeNode struct {
4
* Val int
5
* Left *TreeNode
6
* Right *TreeNode
7
* }
8
*/
9
// BFS
10
func maxDepth(root *TreeNode) int {
11
if root == nil {
12
return 0
13
}
14
15
depth := 1
16
q := []*TreeNode{root, nil} // queue
17
var node *TreeNode
18
for len(q) > 0 {
19
node, q = q[0], q[1:] // pop
20
if node != nil {
21
if node.Left != nil {
22
q = append(q, node.Left)
23
}
24
if node.Right != nil {
25
q = append(q, node.Right)
26
}
27
} else if len(q) > 0 { // 注意要判断队列是否只有一个 nil
28
q = append(q, nil)
29
depth++
30
}
31
}
32
return depth
33
}
Copied!
PHP Code:
1
/**
2
* Definition for a binary tree node.
3
* class TreeNode {
4
* public $val = null;
5
* public $left = null;
6
* public $right = null;
7
* function __construct($value) { $this->val = $value; }
8
* }
9
*/
10
class Solution
11
{
12
13
/**
14
* @param TreeNode $root
15
* @return Integer
16
*/
17
function maxDepth($root)
18
{
19
if (!$root) return 0;
20
21
$depth = 1;
22
$arr = [$root, null];
23
while ($arr) {
24
/** @var TreeNode $node */
25
$node = array_shift($arr);
26
if ($node) {
27
if ($node->left) array_push($arr, $node->left);
28
if ($node->right) array_push($arr, $node->right);
29
} elseif ($arr) {
30
$depth++;
31
array_push($arr, null);
32
}
33
}
34
return $depth;
35
}
36
}
Copied!
复杂度分析
  • 时间复杂度:$O(N)$
  • 空间复杂度:$O(N)$

相关题目

大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。