【LeetCode】104. Maximum Depth of Binary Tree 해법 및 주석, 반복, 깊이 검색
1379 단어 LeetCode
Total Accepted: 137961 Total Submissions: 289093 Difficulty: Easy
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
[분석]
이 문제는 매우 간단하다. 바로 검색 문제이다. 두 갈래 나무를 훑어보고 최대 깊이를 기록하면 문제를 해결할 수 있다. 내가 사용하는 것은 중서 훑어보는 것이다. 물론 다른 훑어봐도 문제를 해결할 수 있다.반복적인 사고방식은 예를 들어 코드의 쓰기 스타일도 효율에 영향을 줄 수 있다. 확장성을 높이는 측면에서 볼 때 중간 반복을 선택하는 것이 좋고 독립 함수로서 집행 효율이 좋다.
[해법 및 주석]
방법1: 모든 결점을 반복하여 최대 깊이를 기록한다
class Solution {
public:
int maxDepth(TreeNode* root)
{
int maxdeep=0;
DFS(root, 0, maxdeep);
return maxdeep;
}
void DFS(TreeNode* root, int deepth,int &maxdeep)
{
if(root==NULL)return;
if(deepth+1>maxdeep)maxdeep=deepth+1;
DFS(root->left,deepth+1,maxdeep);
DFS(root->right,deepth+1,maxdeep);
}
};
방법2: 인터넷 해법, 효율이 높지 않다
class Solution {
public:
int maxDepth(TreeNode *root) {
if (root == NULL) return 0;
TreeNode* left_node = root->left;
TreeNode* right_node = root->right;
int left_dep = maxDepth(left_node);
int right_dep = maxDepth(right_node);
return 1 + ((left_dep > right_dep) ? left_dep:right_dep);
}
};
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.