题目地址
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));
};
如果使用迭代呢？ 我们首先应该想到的是树的各种遍历，由于我们求的是深度，因此 使用层次遍历（BFS）是非常合适的。 我们只需要记录有多少层即可。相关思路请查看binary-tree-traversal
关键点解析
-
队列
-
队列中用 Null(一个特殊元素)来划分每层
-
树的基本操作- 遍历 - 层次遍历（BFS）
代码
/*
* @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;
};
相关题目
书籍推荐
