給定一個(gè)二叉樹(shù)权她，找出其最小深度晤揣。
最小深度是從根節(jié)點(diǎn)到最近葉子節(jié)點(diǎn)的最短路徑上的節(jié)點(diǎn)數(shù)量旗芬。
說(shuō)明: 葉子節(jié)點(diǎn)是指沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)。
示例:
給定二叉樹(shù) [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
答案：
思路是通過(guò)bfs搜索每一層升敲，然后改寫(xiě)每一層的節(jié)點(diǎn)的值為層號(hào)
比如將【3答倡，9，20驴党，null瘪撇，null，15港庄，7】遍歷是改寫(xiě)為【1倔既，2，2,NULL,NULL鹏氧，3渤涌，3】，檢測(cè)到最近的葉子節(jié)點(diǎn)時(shí)返回層號(hào)把还。
/**
* 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;
if(root->left == NULL && root->right == NULL)return 1;
int id = 0 ;
queue<TreeNode*> a;
root->val =1;
a.push(root);
TreeNode* t = root,*f = root;
while(true){
id++;
t = a.front();
a.pop();
if(t->left != NULL){//將左節(jié)點(diǎn)加入隊(duì)列
f = t->left;
f->val = t->val+1;//改寫(xiě)值為層號(hào)
a.push(f);
if(f->right == NULL&&f->left== NULL)return f->val;//檢測(cè)到最近的葉子節(jié)點(diǎn)時(shí)返回層號(hào)
}
if(t->right != NULL){//將右節(jié)點(diǎn)加入隊(duì)列
f = t->right;
f->val = t->val+1;//改寫(xiě)值為層號(hào)
a.push(f);
if(f->right == NULL&&f->left== NULL)return f->val;//檢測(cè)到最近的葉子節(jié)點(diǎn)時(shí)返回層號(hào)
}
}
}
};
