Minimum depth of binary tree (21.4.30)

Given a binary tree to find its minimum depth.

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

NB. Terminal node refers to nodes that do not have branch wires.

Example 1:

Enter: root = [3,9,20, NULL, NULL, 15,7]
Conclusion: 2

Example 2:

Enter: root = [2, null, 3, null, 4, null, 5, null, 6]
Conclusion: 5

The code appears as follows:

    int minDepth(TreeNode* root) {
        if (root==0) return 0;
        int left = minDepth(root->left), right = minDepth(root->right);
        if(right == 0) return left+1;
        if(left == 0) return right+1;
        else return min(left,right)+1; 

This question can be done recursively, but when it works, I found it very slow. It’s about 200ms and there’s also plenty of memory. At least, at least I don’t have any perfect solutions. In the future, I will be tech-savvy and see if I can write better code.

Leave a Comment