Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 31th day 🎈!
🚀 Algorithm 🚀

🌲 Minimum depth of a binary tree

Given a binary tree, find its minimum depth.

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

Note: Leaf nodes are nodes that have no child nodes.

Example 1: 

Enter: root = [3.9.20,null,null,15.7] output:2
Copy the code

Example 2:

The sample2: Enter: root = [2,null,3,null,4,null,5,null,6] output:5
Copy the code

Tip:

  • The range of nodes in the tree is within [0, 105]
  • -1000 <= Node.val <= 1000

🌻C# method: depth-first search

Since we’re solving for the minimum depth of a binary tree, let’s go through the entire binary tree and figure out the depth

Use depth-first search to traverse the entire tree and record the minimum depth.

For each non-leaf node, we only need to calculate the minimum leaf node depth of the left and right subtrees respectively.

This turns a big problem into a small problem that can be solved recursively.

Thinking analytical

Code:

public class Solution {
    public int MinDepth(TreeNode root) {
         if (root == null) return 0;
        else if (root.left == null) return MinDepth(root.right) + 1;
        else if (root.right == null) return MinDepth(root.left) + 1;
        else return Math.Min(MinDepth(root.left), MinDepth(root.right)) + 1; }}Copy the code

The execution result

By execution time:272Ms, in all CBeat 46.32% of users in # submitMemory consumption:50MB, in all CBeat 50.00% of users in submission
Copy the code

Complexity analysis

Time complexity: O(n), where N is the number of nodes in the tree Space complexity: O(H), where H is the height of the treeCopy the code

🌻Java Method 1: Depth-first search

First of all, we can think of a depth-first search method, which traverses the whole tree and records the minimum depth.

For each non-leaf node, we only need to calculate the minimum leaf node depth of the left and right subtrees respectively.

This turns a big problem into a small problem that can be solved recursively.

Code:

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; }}Copy the code

The execution result

By execution time:6Ms, beat out all Java commits60.65% user memory consumption:59MB, beat out all Java commits16.41% of the userCopy the code

Complexity analysis

Time complexity: O(n), where N is the number of nodes in the tree Space complexity: O(H), where H is the height of the treeCopy the code

🌻Java Method 2: breadth-first search

Thinking analytical

Similarly, we can think of using breadth-first search to traverse the entire tree.

When we find a leaf node, we return the depth of the leaf node.

Breadth-first search ensures that the depth of the first searched leaf node must be minimum.

Code:

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; }}Copy the code

The execution result

By execution time:1Ms, beat out all Java commits99.43% user memory consumption:58MB, beat out all Java commits58.59% of the userCopy the code

Complexity analysis

Time complexity: O(n) where n is the number of nodes in the tree Space complexity: O(n) where n is the number of nodes in the treeCopy the code

💬 summary

  • Today is the thirty-first day of clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!