111. Minimum depth of binary tree

Address ：

Power button https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

subject ：

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, 105] Inside -1000 <= Node.val <= 1000

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/minimum-depth-of-binary-tree
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

For topic description, concept description ：

Minimum depth of leaf node = 1

The minimum depth of the parent node depends on its child nodes , Take the minimum value of its minimum depth , add 1

such as ：

node 4, The left child node = 1, The right child node = 1, So node 4 = 1+1

node 2, Only the left child nodes , Then the node 2 = 2+1

The whole diagram shows that the minimum depth of the root node is the minimum depth of traversing its child nodes

Typical recursion

Method 1 、 recursive

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


int minDepth(struct TreeNode* root){
	if(root == NULL)
		return 0;
		
	if(root->left == NULL && root->right == NULL)
		return 1;
		
	int min = INT_MAX;
	
	if(root->left)
	{
		min = fmin(min, minDepth(root->left));
	}
	
	if(root->right)
	{
		min = fmin(min, minDepth(root->right));
	}
	
	return min + 1;
}

One thing to note ：

At the beginning, the commonly used Macro definition minimum

As a result, the last group of big data timed out

// cause timeout
#define mymin(a,b) ( (a) < (b) ? (a) : (b) )

And the reason is that ：

The macro definition is just a simple replacement , If the parameter is a simple number , Actually, no problem

But if the parameter is something that needs to be calculated , Recursive functions are also used here

Then it is calculated once when it is passed in , Calculate again when returning , This magnitude is super large

See more brush notes