【LeetCode】104. Maximum Depth of Binary Tree 해법 및 주석, 반복, 깊이 검색

1379 단어 LeetCode
104. Maximum Depth of Binary Tree
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); 
    }
};

좋은 웹페이지 즐겨찾기