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