[LC111&104] Binary Tree Depth

Wednesday, January 9, 2019

两道算法题分别来自 LeetCode #111 与 LeetCode #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)$