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.
递归的解题思路：
递归当前结点，分一下四种情况考虑：①结点为空时返回0；②结点没有右子树时，返回左子树最小值+1；③结点没有左子树时，返回右子树最小值+1；④当结点双子齐全时，返回左右子树的最小值+1；
注意：
1、注意判断“只有左子树”或“只有右子树”的情况，不要暴力的直接返回左/右子树最小值，因为有可能不存在；
2、省去了“当结点为叶子结点，则返回1”的情况，减少了代码行数，不过会多递归一层，运行时间没有变化；
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int minDepth(TreeNode *root) {
if (!root)
return ; int minLeft = minDepth(root->left);
int minRight = minDepth(root->right); if (minLeft == )
return minRight + ;
else if (minRight == )
return minLeft + ;
else return min(minLeft,minRight) + ;
}
};
【★】迭代的解法：
用按层遍历二叉树的思想，当遍历到第一个叶子结点时，输出此时树的深度，则为最小depth。
用数组保存待遍历的树，设置双指针，一个指向访问当层开始的节点，一个指向访问当层结束节点的下一个位置。
class Solution {
public:
int minDepth(TreeNode *root) {
vector<TreeNode *> treeVec;
treeVec.push_back(root);
int cur = ;
int end;
int depth = ;
if (!root)
return ;
while (cur < treeVec.size()) {
depth++;
end = treeVec.size();
while (cur < end) {
if (!treeVec[cur]->left && \
!treeVec[cur]->right) {
return depth;
}
if (treeVec[cur]->left)
treeVec.push_back(treeVec[cur]->left);
if (treeVec[cur]->right)
treeVec.push_back(treeVec[cur]->right);
cur++;
}
}
}
};
附录：
按层遍历二叉树