111. Minimum depth of a binary tree

LeetCode leetcode-cn.com/problems/mi…

The title

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:

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

    3
   / \
  9  20
    /  \
   15   7
Copy the code

Returns its minimum depth of 2.

Their thinking

DFS, BFS

The minimum depth of a binary tree is given.

Minimum depth: refers to the number of nodes along the shortest path from the root node to the leaf node.

Leaf node: a node that has no left or right child nodes.

So we consider starting from the root node, using the idea of DFS, BFS search.

DFS

Let’s take a look at using DFS (depth-first search) as follows:

  • The root node is empty and returns 0;
  • If the root node is not empty, determine the left and right child nodes:
    • If the left and right child nodes are empty, return 1;
    • If one of the left and right child nodes is empty, return the minimum depth of the non-empty child node.
    • The left and right child nodes are not empty and return the value of the smaller depth among them.

See code Implementation # DFS for details.

BFS

Here, we can also use the BFS (breadth first search) method, we use the BFS method, the search layer by layer, so as long as we find a layer, a node does not have children, then it means that from the root node to the current node is the shortest path.

See code Implementation # BFS for details.

Code implementation

# DFS
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def minDepth(self, root: TreeNode) - >int:
        The root node is empty
        if not root:
            return 0
        # The root node is not empty. Discuss the left and right child nodes separately
        depth = 1

        # The root node is not empty, but there are no left or right children. Return 1
        if not root.left and not root.right:
            return 1
        # No right child exists, return the minimum depth of the left child that is not empty
        elif not root.right:
            depth += self.minDepth(root.left)
        Return the minimum depth of the right child node that is not empty
        elif not root.left:
            depth += self.minDepth(root.right)
        # The left and right child nodes are not empty and return a smaller depth
        else:
            left_depth = self.minDepth(root.left)
            right_depth = self.minDepth(root.right)
            depth += min(left_depth, right_depth)

        return depth

# BFS
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
    def minDepth(self, root: TreeNode) - >int:
        if not root:
            return 0

        from collections import deque
        queue = deque()
        queue.append(root)

        depth = 1

        while queue:
            # Layer by layer search, first record the number of nodes in each layer
            size = len(queue)
            for _ in range(size):
                node = queue.popleft()
                If the current node has no children, the current node is on the minimum path
                if not node.left and not node.right:
                    return depth
                # If one of the nodes is empty, return the minimum depth of nodes that are not empty
                elif not node.right:
                    queue.append(node.left)
                elif not node.left:
                    queue.append(node.right)
                # The left and right child nodes will not be empty
                else:
                    queue.append(node.left)
                    queue.append(node.right)
                
            depth += 1

Copy the code

Achieve results

Welcome to attention

Public Account [Collection of Books]