Minimum Depth of Binary Tree

環(huán)境：python 3.6，scala 2.11.8

題意

給定一個(gè)二叉樹，找出其最小深度。

最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量。

說(shuō)明：葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。

分析

此題與二叉樹的最大深度類似，DFS 思路如下：

• 葉子結(jié)點(diǎn)的定義是左右子節(jié)點(diǎn)都為空的結(jié)點(diǎn)；

• 當(dāng)根節(jié)點(diǎn)左右子節(jié)點(diǎn)都為空時(shí)，maxDepth 和 minDepth 的當(dāng)前小遍歷會(huì)停止；

• 當(dāng)根節(jié)點(diǎn)左右子節(jié)點(diǎn)有一個(gè)為空時(shí)，maxDepth 和 minDepth 會(huì)繼續(xù)遍歷不為空的一側(cè)子節(jié)點(diǎn)；

• 當(dāng)根節(jié)點(diǎn)左右子節(jié)點(diǎn)都不為空時(shí)，maxDepth 和 minDepth 繼續(xù)重復(fù)上述操作。不同的是最終 maxDepth 返回左右子節(jié)點(diǎn)較大深度，minDepth 返回左右子節(jié)點(diǎn)較小深度；

BFS 思路則相對(duì)好理解：

• 對(duì)于同一棵二叉樹，相同的是，若該二叉樹的非根節(jié)點(diǎn)若只有一個(gè)子節(jié)點(diǎn)，minDepth 和 maxDepth 都要繼續(xù)尋找；
• 不同的是，遍歷過(guò)程中，就算遇到葉子節(jié)點(diǎn)，maxDepth 會(huì)尋找更深的葉子結(jié)點(diǎn)，而 minDepth 則可能會(huì)提前結(jié)束遍歷過(guò)程；
• 值得一提的是，相較于使用隊(duì)列，個(gè)人認(rèn)為 scala 寫法 minDepthV3 中 的 flatMap 算子的使用更能體現(xiàn)此題的 BFS 思路；

代碼

python

import collections

def minDepth(root):
    """
    :type root: TreeNode
    :rtype: int
    """
    if not root: return 0
    if not root.left and not root.right: return 1 # 沒(méi)有這個(gè)判斷不影響結(jié)果，只是為了及時(shí)返回
    if not root.left or not root.right:
        return 1 + minDepth(root.left) + minDepth(root.right)
    return 1 + min(minDepth(root.left), minDepth(root.right))


def minDepthV2(root):
    if not root: return 0
    queue = collections.deque([(root, 1)]) # 隊(duì)列保證節(jié)點(diǎn)按層級(jí)關(guān)系有序出隊(duì)
    while queue:
        curr, depth = queue.popleft()
        if curr:
            if not curr.left and not curr.right:
                return depth
            queue.append((curr.left, depth + 1))
            queue.append((curr.right, depth + 1))

scala

import scala.collection.mutable.Queue

object LC111 {

  // 超時(shí) => 超內(nèi)存
//  def minDepth(root: TreeNode): Int = {
//    if (root == null) return 0
//    if (root.left == null & root.right == null) 1
//    if (root.left == null | root.right == null)
//      return 1 + minDepth(root.left) + minDepth(root.right)
//    1 + math.min(minDepth(root.left), minDepth(root.right))
//  }

  def minDepth(root: TreeNode): Int = {
    if (root == null) return 0
    (root.left, root.right) match {
      case (null, null) => 1
      case (null, _) => 1 + minDepth(root.right)
      case (_, null) => 1 + minDepth(root.left)
      case _ => 1 + math.min(minDepth(root.left), minDepth(root.right))
    }
  }

  def minDepthV2(root: TreeNode): Int = {
    if (root == null) return 0
    val q = Queue[(TreeNode, Int)](root, 1)

    while (!q.isEmpty) {
      val (curr, depth) = q.dequeue()
      if (curr != null) {
        if (curr.left == null & curr.right == null) return depth
        q.enqueue((curr.left, depth + 1))
        q.enqueue((curr.right, depth + 1))
      }
    }
    -1
  }
    
  // 層次遍歷
  def minDepthV3(root: TreeNode): Int = {
    def go(currLevel: List[TreeNode]): Int = currLevel.contains(null) match {
      case true => 0
      case false => 
        val nextLevel = currLevel.flatMap{node =>
          val childs: List[TreeNode]  = List(node.left, node.right).filter(_ != null)
          if (childs.isEmpty) List(null)
          else childs
        }
        1 + go(nextLevel)
    }
    go(List(root))
  }
}

最后

歡迎交流和補(bǔ)充