廣度優先搜尋_廣度優先搜尋（BFS）

廣度優先搜尋（breadth-first search）可用于“圖”這種資料結構中，查找最短路徑。

樹是一種特殊的圖，二叉樹是一種特殊的樹。廣度優先搜尋常用于周遊二叉樹，在這個周遊的過程中，需要用到隊列這一先進先出（FIFO）的資料結構。

Queue<Node> queue = new LinkedList<>();
           

廣度優先搜尋是

層級周遊

，它

依次周遊每一層的節點，并将該層所有節點的子節點添加到隊列中，進行下一次周遊，直到周遊結束，隊列為空

。

559. Maximum Depth of N-ary Tree

Loading...​leetcode.com

給定一個樹，找出這個樹的最大深度。

class Solution 
{
    public int maxDepth(Node root) 
    {
        if(root == null)
        {
            return 0;
        }
        
        int maxDepth = 0;//用于記錄最大深度
        Queue<Node> queue = new LinkedList<>();//隊列
        queue.add(root);
        while(!queue.isEmpty())//直到隊列為空，即，周遊完所有的節點
        {
            maxDepth++;//每周遊一層，計數+1
            int size = queue.size();//目前層節點的個數
            for(int i = 0; i < size; i++)
            {
                Node node = queue.poll();//poll()方法，取出隊首節點
                if(node.children != null)//如果存在子節點，需要将子節點依次添加到隊列中，用于下一層周遊
                {
                    List<Node> children = node.children;
                    for(Node child : children)
                    {
                        queue.add(child);
                    }
                }
            }
        }
        return maxDepth;
    }
}
           

111. Minimum Depth of Binary Tree

Loading...​leetcode.com

給定一個二叉樹，求出該二叉樹的最小深度（沒有子節點的節點，距離根節點的最小距離）。

class Solution 
{
    /**
    * 解法：BFS，周遊每一層，找出第一個沒有左右子節點的節點，傳回即可。
    */
    public int minDepth(TreeNode root) 
    {
        if(root == null)
        {
            return 0;
        }
        
        int minDepth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty())
        {
            int size = queue.size();
            minDepth++;
            for(int i = 0; i < size; i++)
            {
                TreeNode node = queue.poll();
                if(node.left == null && node.right == null)//該節點沒有子節點
                {
                    return minDepth;
                }
                if(node.left != null)//左子節點不為空，添加到隊列，進行下一層循環
                {
                    queue.add(node.left);
                }
                if(node.right != null)//右子節點不為空，添加到隊列，進行下一層循環
                {
                    queue.add(node.right);
                }
            }
        }
        return minDepth;
    }
}