[111] Minimum Depth of Binary Tree

[tsungtingdu]

BFS

• 透過 BFS 一層一層往下找，並記錄 level
• 如果有找到 node.left 和 node.right 同時不存在的狀況，那麼就回傳 level
• result:13.54% (超慢 XD)

var minDepth = function(root) {
    if (!root) return 0
    let level = 1
    let queue = [[root]]

    while(queue.length > 0) {
        let nodes = queue.shift()
        let subList = []      
        for (let i = 0; i < nodes.length; i++) {
            if (!nodes[i].left && !nodes[i].right) return level
            if (nodes[i].left) subList.push(nodes[i].left)
            if (nodes[i].right) subList.push(nodes[i].right)
        }
        if (subList.length > 0) {
            queue.push(subList)
            level++
        }
    }
    return level
};

DFS

• 透過 DFS 一層一層往下找，並記錄 level
• 如果有找到 node.left 和 node.right 同時不存在的狀況，那麼就回傳 level
• result:5.70% (更慢 XDDD)

var minDepth = function(root) {
    if (!root) return 0
    return travsers(root, 1)

    function travers(node, level) {
        if (!node.left && !node.right) return level

        let left = node.left ? travers(node.left, level + 1) : Infinity
        let right = node.right ? travers(node.right, level + 1) : Infinity

        return Math.min(left, right)
    }
};

[schiafang]

丟到 queue 裡的 BFS

var minDepth = function(root) {
    if(!root) return 0
    let queue = [[root, 1]] //[node, depth]

    while(queue.length > 0) {
        let [node, depth] = queue.shift()

        if(!node.left && !node.right) return depth  //如果遍歷到 leaf 直接返回深度

        if(node.left) queue.push([node.left, depth + 1]) 
        if(node.right) queue.push([node.right, depth + 1]) 
    }
};

(覺得他是不是有改過 case，不管拿誰的跑都超慢啊XD)

[harrytothemoon]

拿之前的level order來小改就過了 哈哈 result 12%...

var minDepth = function(root) {
    let map = [[0, root]]
    let result = []
    while (map.length) {
        let [level, node] = map.shift()
        if (!node) continue
        if (result[level]) {
            result[level].push(node.val)
        } else {
            result[level] = [node.val]
        }
        if (!node.left && !node.right) break   //加這行
        map.push([level + 1, node.left])
        map.push([level + 1, node.right])
    }
    return result.length
};

分享一個超簡潔recursion作法

    if (root === null) return 0;
    if (root.left === null) return minDepth(root.right) + 1;
    if (root.right === null) return minDepth(root.left) + 1;
    return Math.min( minDepth(root.left), minDepth(root.right) ) + 1;

[windate3411]

遞迴解，找出每一條路徑的深度，最後回傳比較小的結果，5.7%的可悲效能XDD

var minDepth = function(root) {
  if (!root) return 0
  let leftDepth = minDepth(root.left) 
  let rightDepth = minDepth(root.right)
  if (leftDepth === 0 || rightDepth === 0) {
    return rightDepth + leftDepth + 1
  } else {
    return Math.min(leftDepth,rightDepth) + 1
  }
};

[ShihTingJustin]

DFS edge case 之後就剩下有左右節點的狀況，對左右節點做 DFS 的結果取 min，為了避免初始值有問題使用了 Number.MAX_SAFE_INTEGER

var minDepth = function(root) {
    if (root === null) return 0
    if (root.left === null && root.right === null) return 1
    let ans = Number.MAX_SAFE_INTEGER
    if (root.left !== null) ans = Math.min(minDepth(root.left), ans)
    if (root.right !== null) ans = Math.min(minDepth(root.right), ans)
    return ans + 1
};

[henry22]

• 遞迴解

  /**
  * Definition for a binary tree node.
  * function TreeNode(val, left, right) {
  *     this.val = (val===undefined ? 0 : val)
  *     this.left = (left===undefined ? null : left)
  *     this.right = (right===undefined ? null : right)
  * }
  */
  /**
  * @param {TreeNode} root
  * @return {number}
  */
  var minDepth = function(root) {
  if(!root) {
      return 0
  }
  if(!root.left || !root.right) {
      return Math.max(minDepth(root.left), minDepth(root.right)) + 1
  } else {
      return Math.min(minDepth(root.left), minDepth(root.right)) + 1
  }
  };