## 题目地址

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

## 题目描述

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.

## 思路

C++ 解法一：

``````class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
};
``````

Java 解法一：

``````public class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 : (1 + Math.max(maxDepth(root.left), maxDepth(root.right)));
}
}
``````

C++ 解法二：

``````class Solution {
public:
int maxDepth(TreeNode* root) {
if (!root) return 0;
int res = 0;
queue<TreeNode*> q{{root}};
while (!q.empty()) {
++res;
for (int i = q.size(); i > 0; --i) {
TreeNode *t = q.front(); q.pop();
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
return res;
}
};
``````

Java 解法二：

``````public class Solution {
public int maxDepth(TreeNode root) {
if (root == null) return 0;
int res = 0;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
++res;
for (int i = q.size(); i > 0; --i) {
TreeNode t = q.poll();
if (t.left != null) q.offer(t.left);
if (t.right != null) q.offer(t.right);
}
}
return res;
}
}
``````

### 思路2

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

评论
0 评论