最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
递归的遍历左右子树，如果走到一个叶子结点，返回 0 ，比较叶子结点父亲的左右子树高度，返回较小的一棵高度 +1。以后直接返回高度 + 1。
int minDepth(Tree& t){ if(t == NULL) return 0; int left = minDepth(t->left); int right = minDepth(t->right); return (left && right) ? min(left , right) + 1 : left + right + 1; }非递归的解决思路，广度优先遍历找到第一个叶子结点，返回当前深度。
int levelOrder(Tree& t){ if(t == NULL) return 0; TreeNode* p; int depth = 0; queue<TreeNode*> q; q.push(t); while(!q.empty()){ depth += 1; //每进入新的一层 depth++ int width = q.size(); for(int i = 0;i < width;i ++){ p = q.front(); q.pop(); if(p->left == NULL && p->right == NULL) return depth; //最小高度 if(p->left) q.push(p->left); if(p->left) q.push(p->right); } } }代码如下：
#include<iostream> #include<algorithm> using namespace std; typedef struct node{ char val; struct node* left; struct node* right; }TreeNode,*Tree; int minDepth(Tree& t){ if(t == NULL) return 0; int left = minDepth(t->left); int right = minDepth(t->right); return (left && right) ? min(left , right) + 1 : left + right + 1; } void CreateTree(Tree& t){ char x; cin>>x; if(x == '#') t = NULL; else{ t = new TreeNode; t->val = x; CreateTree(t->left); CreateTree(t->right); } } int main(){ Tree t; CreateTree(t); /* a b d # # e # # c # # */ cout<<"minDepth:"<<endl; cout<<minDepth(t); }运行结果：
