8. Maximum Depth of Binary Tree

문제 설명

방법 1 (내가 한 거): 

주어진 트리의 높이를 찾는 문제이다. 나는 depth별로 노드를 방문하는 DFS(pre-order)를 활용했다. 그리하여 각 층에 존재하는 노드를 방문할 때마다 높이 값을 1 늘려주었다. 그 후 그 값들을 vector에 저장하여 최댓값을 찾아냈다.

1. Pre-order traversal을 할 수 있게 기본 틀을 작성한다.

2. 노드를 방문하면 height 값을 1 늘려주고 벡터에 그 값을 넣는다.

3. 트리에 있는 모든 노드들을 다 훑었다면 벡터 속 최댓값을 찾는다.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        vector<int> storage;
        pre_order(root, 0, storage);
        if(root == NULL){
            return 0;
        }
        else{
            return *max_element(storage.begin(), storage.end());
        }
    }
    void pre_order(TreeNode* root, int height, vector<int>& storage){
        if(root == NULL){
            return;
        }
        height += 1;
        storage.push_back(height);
        pre_order(root -> left, height, storage);
        pre_order(root -> right, height, storage);
    }
};

 

방법 2 (해설 참조):

트리의 max depth를 구하기 위해서는 root node기준으로 왼쪽과 오른쪽 트리의 depth 최대값에 1(root node depth)을 더하면 된다. Dp문제 접근방법과 꽤나 유산한듯하다. (root->right) (root->left)를 파라미터로 넣어줌으로 인해 base case에 도달할 때까지 트리 전체를 훑는 듯하는데 대충 느낌은 알겠으나 명확하게 설명은 못하겠다. 

 

Time complexity: O(number of tree nodes)

Space complexity: O(height of the tree)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
     if(root == NULL){
         return 0;
     }
     return max(maxDepth(root->left), maxDepth(root->right))+ 1;
    }
};