每日算法-二叉树的最大深度(树-简单）
题目
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
方法一：dns-深度优先遍历
/**
* @param {TreeNode} root
* @return {number}
*/
function maxDepth(root) { // dns
if (root == null) {
return 0;
} else {
let left = maxDepth(root.left);
let right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}
}
方法二：bfs-广度优先遍历
-
通过数组保存广度遍历对应的结果，依次出队列；
const maxDepth = (root) => { // bfs
if (root == null) return 0;
const queue = [root];
let depth = 1;
while (queue.length) {
// 当前层的节点个数
const levelSize = queue.length;
// 逐个让当前层的节点出列
for (let i = 0; i < levelSize; i++) {
// 当前出列的节点
const cur = queue.shift();
// 左右子节点入列
if (cur.left) queue.push(cur.left);
if (cur.right) queue.push(cur.right);
}
// 当前层所有节点已经出列，如果队列不为空，说明有下一层节点，depth+1
if (queue.length) depth++;
}
return depth;
};
总结
-
深度遍历和广度遍历都能用来遍历树形结构，并获取各节点值。 -
深度遍历也叫前序遍历，先遍历节点的左节点在遍历自身，然后遍历有节点。 -
可用于获取树节点的值，拼接，最大深度，所有路径等算法