[LC111&104] Binary Tree Depth
Wednesday, January 9, 2019
两道算法题分别来自 LeetCode #111 与 LeetCode #104:求搜索二叉树的最小深度和最大深度。使用了 JavaScript 实现。
最小深度
- 除空节点,每递归一次,则层级加一
- 当左子树为空时,则右子树的层级即结果
- 当右子树为空时,则左子树的层级即结果
- 当左右子树都不为空时,分别求左右子树的层级,较小者即结果
function minDepth(root) {
if (root === null) {
return 0
}
if (root.left === null) {
return minDepth(root.right) + 1
}
if (root.right === null) {
return minDepth(root.left) + 1
}
const leftDepth = minDepth(root.left) + 1
const rightDepth = minDepth(root.right) + 1
return Math.min(leftDepth, rightDepth)
}
最大深度
- 除空节点,每递归一次,则层级加一
- 分别求左右子树的层级,较大者即结果
function maxDepth(root) {
if (root === null) {
return 0
}
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}
复杂度分析
对于拥有 N
个元素的搜索二叉树:
- 时间复杂度:由于每个节点都会遍历一次,所以时间复杂度为 $O(N)$
- 空间复杂度:最坏的情况下,搜索二叉树退化成线性链表,即每个结点最多只有一个子结点,则函数递归的次数达到 $N$ 次,其对应的空间复杂度为 $O(N)$;最好的情况下,搜索二叉树是一颗平衡二叉树,则函数递归的次数为二叉树的深度 $logN$,则对应的空间复杂度为 $O(logN)$