一.题目：二叉树的最小深度
二.算法思想
（1）递归
一定要注意比如如果结点无左结点而有右结点时，此时要看右子树的最小深度（注意加1），因为如果题目定义的是“根结点到最近的叶结点”，所以别误以为因为左子树为空所以此时深度为1。
如果左子树和右子树都不为空时，则返回左右子树的最小深度+1。
（2）迭代
利用层次遍历，当遇到叶结点（指针的左孩子和右孩子都为空）的时候就表示最先碰“底”，模板。
三.代码
（1）递归代码
/** * Definition for a binary tree node. * 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 0; if(!root->left) return minDepth(root->right)+1; if(!root->right) return minDepth(root->left)+1; return min(minDepth(root->right),minDepth(root->left))+1; } };
（2）迭代代码
1./** * Definition for a binary tree node. * 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==NULL) return 0; TreeNode* node; queue<TreeNode*>que; int depth=1; que.push(root); while(!que.empty()){ int num=que.size(); while(num-->0){//处理每一层 node=que.front(); que.pop(); if(!node->left&&!node->right) return depth; if(node->left) que.push(node->left); if(node->right) que.push(node->right); } depth++; } return depth; } };
