题目描述
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
题目链接:104. 二叉树的最大深度
思路
由于树是一种递归的数据结构,因此用递归去解决的时候往往非常容易。
用递归实现的代码如下:
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));
};
二叉数的遍历主要有前中后遍历和层次遍历。 前中后属于 DFS,层次遍历则可以使用 BFS 或者 DFS 来实现。只不过使用 BFS 来实现层次遍历会容易些。
对于此题我们首先应该想到的是树的各种遍历,由于我们求的是深度,因此 使用层次遍历(BFS)是非常合适的。 我们只需要记录有多少层即可。
关键点:
- 队列
- 队列中用 Null(一个特殊元素)来划分每层,或者在对每层进行迭代之前保存当前队列元素的个数(即当前层所含元素个数)
- 树的基本操作- 遍历 - 层次遍历(BFS)
代码:
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;
};
总结:
本题主要考察二叉树的各种遍历方式,要求熟练掌握,此外还应掌握递归的使用。
标签:BFS,遍历,return,queue,二叉树,深度,root,leetcode From: https://blog.51cto.com/codeniu/6293347