# 0104. 二叉树的最大深度

### 题目地址（104. 二叉树的最大深度）

<https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/description/>

### 题目描述

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

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

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

示例：
给定二叉树 [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<TreeNode*>();
        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<TreeNode> queue = new LinkedList<TreeNode>();
        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 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

![](https://p.ipic.vip/2m75d5.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/easy/104.maximum-depth-of-binary-tree.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.