leetcode:111. Minimum depth of binary tree

111. Minimum depth of binary tree

source ： Power button （LeetCode）

link : https://leetcode.cn/problems/minimum-depth-of-binary-tree

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 1：
Input ：root = [3,9,20,null,null,15,7]
Output ：2

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

Tips ：

• The number of nodes in the tree ranges from $[0,10^5]$ Inside
• $-1000<=Node.val<=1000$

solution

• recursive ： Start at the root node , If the node is empty , Then return to 0; If not for 0, Recursively call to find the depth of the left and right subtrees , The final result is... Of the root node 1 layer + min(left, right), Pay attention here , If one of the left and right child nodes is empty , It is necessary to continue to go down to non empty nodes

  • The definition of leaf node is that the left child and the right child are null It's called leaf node
  • When root Both the left and right children of the node are empty , return 1
  • When root One of the left and right children of the node is empty , Returns the depth of a child node that is not empty
  • When root The children around the node are not empty , Return the node value of the smaller depth of the left and right children

• bfs loop : bfs Sequence traversal , When traversing to a node, the left and right child nodes are empty , Is the minimum depth of the tree

Code implementation

recursive

python Realization

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        if not root.left and not root.right:
            return 1
        
        if not root.left:
            return 1 + self.minDepth(root.right)
        
        if not root.right:
            return 1 + self.minDepth(root.left)
        
        return 1 + min(self.minDepth(root.left), self.minDepth(root.right))

c++ Realization

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    int minDepth(TreeNode* root) {
     
        if (root == nullptr)
            return 0;
        if (root->left == nullptr && root->right == nullptr)
            return 1;
        if (root->left == nullptr)
            return 1 + minDepth(root->right);
        if (root->right == nullptr)
            return 1 + minDepth(root->left);

        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

Complexity analysis

• Time complexity ： $O(N)$ Each node is traversed once
• Spatial complexity ： $O(height)$ height Is the height of the binary tree , Recursion requires stack space , Stack space depends on the depth of recursion

BFS loop

python Realization

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        
        # bfs
        dq = []
        dq.append((1, root))
        while dq:
            depth, node = dq.pop(0)
            if not node.left and not node.right:
                return depth
            if node.left:
                dq.append([depth+1, node.left])
            if node.right:
                dq.append([depth+1, node.right])
        return depth

c++ Realization

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */
class Solution {
    
public:
    int minDepth(TreeNode* root) {
    
        if (root == nullptr)
            return 0;
        
        int depth = 1;
        deque<pair<TreeNode*, int>> dq;
        dq.push_back({
    root, 1});

        while (dq.size() != 0) {
    
            TreeNode* node = dq.front().first;
            int depth = dq.front().second;

            dq.pop_front();
            if (node->left == nullptr && node->right == nullptr)
                return depth;
            
            if (node->left != nullptr)
                dq.push_back({
    node->left, depth+1});
            
            if (node->right != nullptr)
                dq.push_back({
    node->right, depth+1});
        }
        return depth;


    }
};

Complexity analysis

• Time complexity ： $O(N)$
• Spatial complexity ： $O(N)$

Reference resources

• c++ pair