> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/104.maximum-depth-of-binary-tree.md).
# 0104. 二叉树的最大深度
### 题目地址（104. 二叉树的最大深度）
### 题目描述
```
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
```
### 前置知识
* [递归](/leetcode-solution/thinkings/dynamic-programming.md)
### 公司
* 阿里
* 腾讯
* 百度
* 字节
* apple
* linkedin
* uber
* yahoo
### 思路
由于树是一种递归的数据结构，因此用递归去解决的时候往往非常容易，这道题恰巧也是如此，
* 用递归实现的代码如下：
```js
var maxDepth = function (root) {
if (!root) return 0;
if (!root.left && !root.right) return 1;
return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
};
```
如果使用迭代呢？ 我们首先应该想到的是树的各种遍历，由于我们求的是深度，因此 使用层次遍历（BFS）是非常合适的。 我们只需要记录有多少层即可。相关思路请查看[binary-tree-traversal](/leetcode-solution/thinkings/binary-tree-traversal.md)
### 关键点解析
* 队列
* 队列中用 Null(一个特殊元素)来划分每层，或者在对每层进行迭代之前保存当前队列元素的个数（即当前层所含元素个数）
* 树的基本操作- 遍历 - 层次遍历（BFS）
### 代码
* 语言支持：JS，C++，Java，Python, Go, PHP
JS Code:
```js
/*
* @lc app=leetcode id=104 lang=javascript
*
* [104] Maximum Depth of Binary Tree
*/
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
var maxDepth = function (root) {
if (!root) return 0;
if (!root.left && !root.right) return 1;
// 层次遍历 BFS
let cur = root;
const queue = [root, null];
let depth = 1;
while ((cur = queue.shift()) !== undefined) {
if (cur === null) {
// 注意⚠️： 不处理会无限循环，进而堆栈溢出
if (queue.length === 0) return depth;
depth++;
queue.push(null);
continue;
}
const l = cur.left;
const r = cur.right;
if (l) queue.push(l);
if (r) queue.push(r);
}
return depth;
};
```
C++ Code:
```
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == nullptr) return 0;
auto q = vector();
auto d = 0;
q.push_back(root);
while (!q.empty())
{
++d;
auto sz = q.size();
for (auto i = 0; i < sz; ++i)
{
auto t = q.front();
q.erase(q.begin());
if (t->left != nullptr) q.push_back(t->left);
if (t->right != nullptr) q.push_back(t->right);
}
}
return d;
}
};
```
Java Code:
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
if(root == null)
{
return 0;
}
// 队列
Queue queue = new LinkedList();
queue.offer(root);
int res = 0;
// 按层扩展
while(!queue.isEmpty())
{
// 拿出该层所有节点，并压入子节点
int size = queue.size();
while(size > 0)
{
TreeNode node = queue.poll();
if(node.left != null)
{
queue.offer(node.left);
}
if(node.right != null)
{
queue.offer(node.right);
}
size-=1;
}
// 统计层数
res +=1;
}
return res;
}
}
```
Python Code:
```python
class Solution:
def maxDepth(self, root: TreeNode) -> int:
if not root: return 0
q, depth = [root, None], 1
while q:
node = q.pop(0)
if node:
if node.left: q.append(node.left)
if node.right: q.append(node.right)
elif q:
q.append(None)
depth += 1
return depth
```
Go Code:
```go
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
// BFS
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
depth := 1
q := []*TreeNode{root, nil} // queue
var node *TreeNode
for len(q) > 0 {
node, q = q[0], q[1:] // pop
if node != nil {
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
} else if len(q) > 0 { // 注意要判断队列是否只有一个 nil
q = append(q, nil)
depth++
}
}
return depth
}
```
PHP Code:
```php
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution
{
/**
* @param TreeNode $root
* @return Integer
*/
function maxDepth($root)
{
if (!$root) return 0;
$depth = 1;
$arr = [$root, null];
while ($arr) {
/** @var TreeNode $node */
$node = array_shift($arr);
if ($node) {
if ($node->left) array_push($arr, $node->left);
if ($node->right) array_push($arr, $node->right);
} elseif ($arr) {
$depth++;
array_push($arr, null);
}
}
return $depth;
}
}
```
**复杂度分析**
* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$
### 相关题目
* [102.binary-tree-level-order-traversal](/leetcode-solution/medium/102.binary-tree-level-order-traversal.md)
* [103.binary-tree-zigzag-level-order-traversal](/leetcode-solution/medium/103.binary-tree-zigzag-level-order-traversal.md)
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
