主題
難度: Easy
===========================================================================
給予二元樹,找尋最小深度,
最小深度表示,由根節點到葉節點,最短路徑的節點數
注意:葉節點是沒有子節點的節點
===========================================================================
測資:
Input: root = [3,9,20,null,null,15,7]
Output: 2
===========================================================================
條件限制:
二元樹的節點數量為0~10^5
-1000 <= Node.val <= 1000
===========================================================================
解題:
本題採用BFS進行解題,
一層層的往下搜尋,若該層有節點為葉節點,則返回目前的層數
public class Solution
{
Queue<TreeNode> treeNodes = new Queue<TreeNode>(); //用來儲存該層未搜索的節點
int result = 0; //當前層數
public int MinDepth(TreeNode root)
{
if (root == null)
return 0;
treeNodes.Enqueue(root);
while(treeNodes!=null)//若佇列為空表示已搜尋完所有節點
{
result++; //計算目前第幾層
int nodes_count = treeNodes.Count; //當前層數有幾個節點
for (int i=0;i< nodes_count; i++) //取出本層的所有節點
{
TreeNode node = treeNodes.Dequeue();
if(node.left==null && node.right==null) //若遇到葉節點則為最短路徑;
return result;
if(node.left!=null) //若有子節點,則非葉節點,需放入佇列下輪繼續搜尋
treeNodes.Enqueue(node.left);
if(node.right!=null)
treeNodes.Enqueue(node.right);
}
}
return result;
}
}
達人
