Leetcode skimming: binary tree 09 (minimum depth of binary tree)

111. Minimum depth of binary tree

Force button topic link

Given a binary tree , Find out the minimum depth .

The minimum depth is the number of nodes on the shortest path from the root node to the nearest leaf node .

explain : A leaf node is a node that has no children .

Example :

Given binary tree [3,9,20,null,null,15,7],

Return its minimum depth 2.

Still use sequence traversal , When this layer is dissatisfied , And ！！！ A leaf node appears , Then the minimum depth appears .

package com.programmercarl.tree;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/** * @ClassName MinDepth * @Descriotion TODO * @Author nitaotao * @Date 2022/7/3 22:32 * @Version 1.0 * 111.  Minimum depth of binary tree  * https://leetcode.cn/problems/minimum-depth-of-binary-tree/ **/
public class MinDepth {
    
    public int minDepth(TreeNode root) {
    
        // Sequence traversal , Which line is dissatisfied , Default , Is the shortest depth 
        int minDepth = 0;
        if (root == null) {
    
            return minDepth;
        }
        Deque<TreeNode> deque = new ArrayDeque<TreeNode>();
        deque.offer(root);
        int length = 1;
        while (!deque.isEmpty()) {
    
            int size = deque.size();
            boolean flag = false;
            while (size > 0) {
    
                root = deque.poll();
                // Leaf nodes appear 
                if (root.left == null && root.right == null) {
    
                    flag = true;
                }
                if (root.left != null) {
    
                    deque.offer(root.left);
                }
                if (root.right != null) {
    
                    deque.offer(root.right);
                }
                size--;
            }
            length *= 2;
            minDepth++;
            if (deque.size() != length && flag) {
    
                return minDepth;
            }
        }
        return minDepth;
    }
}