Open
Description
方法一:递归
解题思想:
二叉树的最大深度即为左子树的深度与右子树深度的较大值 + 1,而求子树的深度一样可以用这个方法计算。
一直递归到空节点结束。
代码:
var maxDepth = function(root) {
if (!root) return 0;
if (root.left === null && root.right === null) {
return 1;
}
const leftDepth = maxDepth(root.left) + 1;
const rightDepth = maxDepth(root.right) + 1;
return Math.max(leftDepth, rightDepth);
};
复杂度分析:
- 时间复杂度:O(n):n取决于二叉树的节点数量,因为每个节点都只遍历一次。
- 空间复杂度:O(height):height为二叉树的高度,递归函数需要栈空间,而栈空间取决于递归的深度,因此空间复杂度等价于二叉树的高度。
方法二:广度优先搜索
TODO