Links

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 。

前置知识

公司

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

思路

由于树是一种递归的数据结构,因此用递归去解决的时候往往非常容易,这道题恰巧也是如此,
  • 用递归实现的代码如下:
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

关键点解析

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

代码

  • 语言支持:JS,C++,Java,Python, Go, PHP
JS 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;
}
};
Java Code:
/**
* 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:
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:
/**
* 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:
/**
* 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)$

相关题目

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