LeetCode_minimum-depth-of-binary-tree
2002 ワード
minimum-depth-of-binary-tree
リンク:https://www.nowcoder.com/practice/e08819cfdeb34985a8de9c4e6562e724?tpId=46&tqId=29030&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-rankingソース:牛客網
タイトルの説明:
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.
リーフノードに到達する最短距離(通過するノード数)を見つける.
解題の考え方:この問題はmaximum-depthと似ていて、違いは、最小の深さを判断することです.1つの葉の判断を増やさなければならない(1つのノードが左サブツリーまたは右サブツリーのみであれば、左右のサブツリーの中から小さいものを深さとして取ることはできないので、それは0になるので、私たちは葉ノードでしか深さを判断できないが、最大深さを求めるときは、必ず大きいものを取るので、この問題はない).
リンク:https://www.nowcoder.com/practice/e08819cfdeb34985a8de9c4e6562e724?tpId=46&tqId=29030&tPage=1&rp=1&ru=/ta/leetcode&qru=/ta/leetcode/question-rankingソース:牛客網
タイトルの説明:
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.
リーフノードに到達する最短距離(通過するノード数)を見つける.
解題の考え方:この問題はmaximum-depthと似ていて、違いは、最小の深さを判断することです.1つの葉の判断を増やさなければならない(1つのノードが左サブツリーまたは右サブツリーのみであれば、左右のサブツリーの中から小さいものを深さとして取ることはできないので、それは0になるので、私たちは葉ノードでしか深さを判断できないが、最大深さを求めるときは、必ず大きいものを取るので、この問題はない).
class Solution {
public:
int run(TreeNode *root) {
if (root==NULL)
return 0;
if (root->left==NULL)
return run(root->right)+1;
if (root->right==NULL)
return run(root->left)+1;
int left = run(root->left);
int right = run(root->right);
return left<right?left+1:right+1;
}
};