111. Minimum Depth of Binary Tree

• issue 3%：Caculate minimum depth of binary tree. Find the shortest path from top-node to bottom-node.

• Expected Result 3% ： Return the shortest path from top(root) to bottom(leaf).

• Conditions 4%: The leaf is defined that a node which doesn't have any childred(left/right).

• Logics of Examples 20%：
  1.使用 DSF 去追蹤每個 leaf, 最後回傳最小路徑(慢但省 memory)
  2.使用 BFS 去追蹤每個 leaf, 最後回傳最小路徑(快但耗 memory)

• Issue & Expected Result & Conditions

  • Caculate minimum depth of binary tree. Find the shortest path from top-node to bottom-node and Return it. The leaf is defined that a node which doesn't have any childred(left/right). Therefore, we will keep tack of each node until getting the shortest path to any leaf.

• Logic of examples

  • The tree starts with 3 on top. And it has 3 leaves 9, 15, and 7. Form top to the closest leaf is 9 by counting path legth. So, we return 2.
    

• Talk about solution 70% ：英文

  • By using Depth First Search(DFS) to keep track of each node, space complexity is reduced to O(maxdepth) instead of BFS's O(n). But Time complexity is increased to O(maxdepth) rather than Breadth First Search(BFS) O(mindepth).

  • BFS Algorithom has to increase memory to save the siblings. But its advantage is that if we met the first leaf and the leaf must be the minDepth leaf. Therefore, we couldn't keep trace all the nodes.
    

    
    圖片來源：https://docs.oracle.com/cd/E19509-01/820-3742/ghpow/index.html

• 結語：使用什麼演算法取決於場景（舉些例子）

  • Using BFS/DFS is depending on scenarios. Embedded System which has limited memory, so it could choose DFS. Wheseas, if some applications is more care about efficiency, they could choose BFS.

• DFS
  

  
  

• BFS