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