主題

[LeetCode C#] 111. Minimum Depth of Binary Tree - Binary tree, Breadth-First Search

帥氣跳蚤蛋 | 2021-07-24 00:02:56 | 巴幣 0 | 人氣 86

難度: 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;
    }
}

創作回應

相關創作

更多創作