深度优先遍历 DFS
解题思路
一个树的最大深度 = 根节点的高度 + 子树的最大深度中的较大者
复杂度
-
时间复杂度：
O(n)，其中 n 为二叉树节点的个数，每个节点在递归中只被遍历一次； -
空间复杂度：
O(height)，其中 height 表示二叉树的高度，递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于二叉树的高度；- 在平均情况下，二叉树的高度与节点个数为对数关系，即
O(logN)； - 而在最坏情况下，树形成链状，空间复杂度为
O(N)；
- 在平均情况下，二叉树的高度与节点个数为对数关系，即
实现代码
var maxDepth = function (root) {
let res = 0;
if (root === null) return res;
for (const node of root.children) {
res = Math.max(res, maxDepth(node));
}
return res + 1;
};
广度优先遍历 BFS
解题思路
使用层序遍历二叉树，因为最大的深度就是二叉树的层数；
在二叉树中，一层一层的来遍历二叉树，记录一下遍历的层数就是二叉树的深度；
复杂度
-
时间复杂度：
O(n)，n 是二叉树节点数目，每个节点会被遍历一次； -
空间复杂度：
O(n)
实现代码
var maxDepth = function (root) {
let res = 0;
if (root === null) return res;
const queue = [];
queue.push(root);
while (queue.length) {
let len = queue.length;
while (len) {
const node = queue.shift();
node.children.forEach(item => {
queue.push(item);
});
len--;
}
res++;
}
return res;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 429. N 叉树的层序遍历
上一篇
评论
