Binary tree -- 111. Minimum depth of binary tree

1 Title Description

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 .

2 Title Example

Example 2：

Input ：root = [2,null,3,null,4,null,5,null,6]
Output ：5

3 Topic tips

The number of nodes in the tree ranges from [0, 105] Inside
-1000 <= Node.val <= 1000

4 Ideas

Method 1 : Depth-first search
First of all, you can think of the method of using depth first search , Traverse the whole tree , Record the minimum depth .
For every non leaf node , We only need to calculate the minimum leaf node depth of its left and right subtrees . In this way, a big problem is transformed into a small problem , This problem can be solved recursively .
Complexity analysis
Time complexity :O(N), among N Is the number of nodes in the tree . Access once for each node .
· Spatial complexity :O(H), among H Is the height of the tree . The space complexity mainly depends on the overhead of stack space during recursion , In the worst case , The trees are in chains , The space complexity is O(N). On average, the height of the tree is positively correlated with the logarithm of the number of nodes , The space complexity is O(log N).
Method 2 : Breadth first search
Again , We can think of using breadth first search , Traverse the whole tree . When we find a leaf node , Directly return the depth of this leaf node . The nature of breadth first search ensures the depth of the leaf node first searched — Fixed minimum .
Complexity analysis
Time complexity :O(N), among N Is the number of nodes in the tree . Access once for each node .
· Spatial complexity :O(N), among N Is the number of nodes in the tree . The space complexity mainly depends on the overhead of the queue , The number of elements in the queue will not exceed the number of nodes in the tree .

5 My answer

Method 1 : Depth-first search

class Solution {
    
    public int minDepth(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }

        if (root.left == null && root.right == null) {
    
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
    
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
    
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

Method 2 : Breadth first search

class Solution {
    
    class QueueNode {
    
        TreeNode node;
        int depth;

        public QueueNode(TreeNode node, int depth) {
    
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
    
        if (root == null) {
    
            return 0;
        }

        Queue<QueueNode> queue = new LinkedList<QueueNode>();
        queue.offer(new QueueNode(root, 1));
        while (!queue.isEmpty()) {
    
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node;
            int depth = nodeDepth.depth;
            if (node.left == null && node.right == null) {
    
                return depth;
            }
            if (node.left != null) {
    
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            if (node.right != null) {
    
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }

        return 0;
    }
}