111. Minimum depth of binary tree

111. Minimum depth of binary tree

Given a binary tree , Find out the maximum depth .

The depth of a binary tree is the number of nodes in the longest path from the root node to the farthest leaf node .

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

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

    3
   / \
  9  20
    /  \
   15   7
 Return to its maximum depth  3 

Ideas （dfs）

Reference to others , Post link

Stupid pig blasting group

Source code

class Solution {
    
public:
    int minDepth(TreeNode* root) {
    
        if (root == nullptr) {
     //  If the initial root node is empty , Then return to 0
            return 0;
        }
        if (root->left && root->right) {
    //  If you change the node, both your sons have , Returns the minimum depth of recursion , Add 1（ The height of the node itself is taken into account ）
            return 1 + min(minDepth(root->left),minDepth(root->right));
        }
        else if (root->left) {
    //  If only the left son , His left son , Depth plus 1
            return 1 + minDepth(root->left);
        }
        else if (root->right) {
    //  If only the left son , Recursive its right son , Depth plus 1
            return 1 + minDepth(root->right);
        }
        else {
    //  Without a son , Then the depth increases 1（ The height of the node itself is taken into account ）
            return 1;
        }
        
    }
};

Ideas （ queue ）

Self use pair Construct a data structure , Record the node and path depth respectively , Then construct such a queue .
Because of the nature of queues , Each time, all the steps of the latest step are recorded in , Therefore, the first leaf node that meets the requirements must be the shortest path

Source code

class Solution {
    
public:
    int minDepth(TreeNode* root) {
    
        if (root == nullptr) {
    
            return 0;
        }
        queue<pair<TreeNode*,int>> queue;//  Construct data structures , The first storage node , Second storage depth  
        queue.push(pair(root,1));

        while (!queue.empty()) {
    
            TreeNode* node = queue.front().first;
            int depth = queue.front().second;
            queue.pop();
            if (node->left == nullptr && node->right == nullptr) {
    //  The node returns the leaf depth 
                return depth;
            }
            if (node->left != nullptr) {
    
                queue.push(pair(node->left,depth+1));//  Remember to add one to the depth 
            }
            if (node->right != nullptr) {
    
                queue.push(pair(node->right,depth+1));//  Remember to add one to the depth 
            }
        }

        return 0;
    }
};