Fetching contributors…
Cannot retrieve contributors at this time
153 lines (128 sloc) 3.58 KB

## 题目地址

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

## 题目描述

``````Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

Example:

Given binary tree [3,9,20,null,null,15,7],

3
/ \
9  20
/  \
15   7
return its depth = 3.

``````

## 思路

```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));
};```

## 关键点解析

• 队列

• 队列中用 Null(一个特殊元素)来划分每层，或者在对每层进行迭代之前保存当前队列元素的个数（即当前层所含元素个数）

• 树的基本操作- 遍历 - 层次遍历（BFS）

## 代码

• 语言支持：JS，C++，Python

JavaScript Code:

```/*
* @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;
}
};```

Python Code:

```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```

## 相关题目

You can’t perform that action at this time.