题目描述
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7]
,
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
题意:求一棵二叉树的叶节点最小深度。
算法1
题解:如果左右子树都不为空,那么树的最小深度等于左右子树的最小值加上1;如果左右子树至少有一个为空,那么树的深度等于左右子树的最大值加上1。(因为求的是叶节点的最小深度,如果子树为空就不能考虑这半边了)
C++ 代码
int minDepth(TreeNode* root) {
if(root == NULL) return 0;
int left = minDepth(root->left);
int right = minDepth(root->right);
if(left == 0 || right == 0)
return 1 + max(left,right);
return 1 + min(left,right);
}