[LC111&104] Binary Tree Depth

Wednesday, January 9, 2019

两道算法题分别来自 LeetCode #111LeetCode #104:求搜索二叉树的最小深度和最大深度。使用了 JavaScript 实现。

depth of binary tree

最小深度

  • 除空节点,每递归一次,则层级加一
  • 当左子树为空时,则右子树的层级即结果
  • 当右子树为空时,则左子树的层级即结果
  • 当左右子树都不为空时,分别求左右子树的层级,较小者即结果
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)$