【leetcode c++】111 Minimum Depth of Binary Tree
1177 ワード
Minimum Depth of Binary Tree
Given a binary tree, find its minimumdepth.
The minimum depth is the number of nodesalong the shortest path from the root node down to the nearest leaf node.
前に最大深さという問題をしました.この問題は最小深さを求めています.最大深さを求めるとき、私はわざと現在のノードがリーフノードかどうかを区別していません.なぜなら、リーフノードかどうかにかかわらず、各ノードには現在の深さがあります.最大深さを見つければいいので、「すべてのノードの最大深さを探す」に相当します.この問題は、「葉を探すノードの深さの中で一番小さい」に相当します.だから私たちは葉のノードの時に判断し、他のノードは遍歴し続けます.同様に、Maximum Depth of Binary Treeの問題のコードを変更することもできます.
Given a binary tree, find its minimumdepth.
The minimum depth is the number of nodesalong the shortest path from the root node down to the nearest leaf node.
前に最大深さという問題をしました.この問題は最小深さを求めています.最大深さを求めるとき、私はわざと現在のノードがリーフノードかどうかを区別していません.なぜなら、リーフノードかどうかにかかわらず、各ノードには現在の深さがあります.最大深さを見つければいいので、「すべてのノードの最大深さを探す」に相当します.この問題は、「葉を探すノードの深さの中で一番小さい」に相当します.だから私たちは葉のノードの時に判断し、他のノードは遍歴し続けます.同様に、Maximum Depth of Binary Treeの問題のコードを変更することもできます.
/**
* 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(NULL == root) return 0;
int lv = 0;
int minLv = -1;
Lv(root, lv, minLv);
return minLv + 1;
}
void Lv(TreeNode* root, int lv, int& minLv) {
if(NULL == root) return;
if(!root->left && !root->right)
{
if(-1 == minLv || lv < minLv) minLv = lv;
}
Lv(root->left, lv + 1, minLv);
Lv(root->right, lv + 1, minLv);
}
};