[Leetcode 문제풀이] Leetcode 111: 두 갈래 나무의 최소 깊이[귀속/비귀속 구해/대기열]
2435 단어 풀다
LeetCode 111: 두 갈래 나무의 최소 깊이
두 갈래 나무의 최소 깊이를 구하다.최소 깊이는 나무의 뿌리 결점에서 가장 가까운 잎 결점까지의 가장 짧은 경로에서 결점의 수량을 가리킨다.
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. struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
1 귀속 구해
class Solution {
public:
int run(TreeNode *root) {
int minimum = 0;
if(root==NULL)
{
return minimum;
}
int ld = run(root->left); //
int rd = run(root->right);
if(ld * rd > 0) //
{
return (ld>rd?rd:ld)+1;
}
else // 0,
{
return (ld>rd?ld:rd)+1;
}
}
};
class Solution
{
public:
int run(TreeNode* root)
{
if (root == nullptr) return 0;
if (root->left == nullptr) return run(root->right) + 1;
if (root->right == nullptr) return run(root->left) + 1;
return min(run(root->left) , run(root->right)) + 1;
}
};
2 비귀속, BFS
class Solution {
public:
int run(TreeNode *root) {
if(root == NULL)
return 0;
queue que;
que.push(root);
int depth = 0;
while(!que.empty())
{
int size = que.size(); //
depth++;
//
for(int i = 0; i < size; ++i)
{
TreeNode* tmp = que.front();
if(tmp->left != NULL)
que.push(tmp->left);
if(tmp->right != NULL)
que.push(tmp->right);
que.pop();
// ,
if(tmp->left == NULL && tmp->right == NULL)
return depth;
}
}
return -1;
}
};
C++queue 복습 요약
FIFO는 임의로 액세스할 수 없습니다. #include
using namespace std;
queue queT; //queue ,queue :
push(elem);//
pop(); //
back(); //
front(); //
queue& operator=(const queue &que);//
empty(); // , true
size(); //
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
낙곡 P1040 플러스 두 갈래 나무
제목:
n n n 개의 노드가 있는 두 갈래 나무는 노드마다 하나의 점수가 있고 모든 자나무에도 점수가 있다.
각 자나무의 점수 계산 방법은 다음과 같다.× 오른쪽에 있는 나무의 가산점인 ubtr의 뿌리 점수.sub...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
int run(TreeNode *root) {
int minimum = 0;
if(root==NULL)
{
return minimum;
}
int ld = run(root->left); //
int rd = run(root->right);
if(ld * rd > 0) //
{
return (ld>rd?rd:ld)+1;
}
else // 0,
{
return (ld>rd?ld:rd)+1;
}
}
};
class Solution
{
public:
int run(TreeNode* root)
{
if (root == nullptr) return 0;
if (root->left == nullptr) return run(root->right) + 1;
if (root->right == nullptr) return run(root->left) + 1;
return min(run(root->left) , run(root->right)) + 1;
}
};
class Solution {
public:
int run(TreeNode *root) {
if(root == NULL)
return 0;
queue que;
que.push(root);
int depth = 0;
while(!que.empty())
{
int size = que.size(); //
depth++;
//
for(int i = 0; i < size; ++i)
{
TreeNode* tmp = que.front();
if(tmp->left != NULL)
que.push(tmp->left);
if(tmp->right != NULL)
que.push(tmp->right);
que.pop();
// ,
if(tmp->left == NULL && tmp->right == NULL)
return depth;
}
}
return -1;
}
};
#include
using namespace std;
queue queT; //queue ,queue :
push(elem);//
pop(); //
back(); //
front(); //
queue& operator=(const queue &que);//
empty(); // , true
size(); //
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
낙곡 P1040 플러스 두 갈래 나무제목: n n n 개의 노드가 있는 두 갈래 나무는 노드마다 하나의 점수가 있고 모든 자나무에도 점수가 있다. 각 자나무의 점수 계산 방법은 다음과 같다.× 오른쪽에 있는 나무의 가산점인 ubtr의 뿌리 점수.sub...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.