Dec 25, 2024

515. Find Largest Value in Each Tree Row

내 코드

BFS

0ms, 22.80MB

/**
 * 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:
    vector<int> largestValues(TreeNode* root) {
        vector<int> answer;
        if(root == nullptr) return answer;

        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
            int maxValue{INT_MIN}; // - 2^31 ~ 2^31 - 1
            for(int s{}, e{static_cast<int>(q.size())}; s < e; ++s) {
                TreeNode* now = q.front(); q.pop();
                maxValue = max(maxValue, now->val);
                
                if(now->left) q.push(now->left);
                if(now->right) q.push(now->right);
            }
            answer.push_back(maxValue);
        }
        return answer;
    }
};

Solution

Approach 1: Breadth First Search (BFS)

0ms, 22.65MB
Complexity
- Given $n$ as the number of nodes in the tree.
- Time Complexity: $O(n)$
- Space Complexity: $O(n)$

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (root == nullptr) {
            return vector<int>{};
        }
        
        vector<int> ans;
        queue<TreeNode*> queue;
        queue.push(root);
        
        while (!queue.empty()) {
            int currentLength = queue.size();
            int currMax = INT_MIN;
            
            for (int i = 0; i < currentLength; i++) {
                TreeNode* node = queue.front();
                queue.pop();
                currMax = max(currMax, node->val);
                
                if (node->left) {
                    queue.push(node->left);
                }
                
                if (node->right) {
                    queue.push(node->right);
                }
            }
            
            ans.push_back(currMax);
        }
        
        return ans;
    }
};

GPT

이 코드는 이진 트리의 각 레벨에서 가장 큰 값을 찾는 알고리즘을 구현한 것입니다. 이를 단계별로 설명하겠습니다.

코드 분석

1. 함수 정의와 초기 확인

vector<int> largestValues(TreeNode* root) {
    if (root == nullptr) {
        return vector<int>{};
    }

largestValues 함수는 이진 트리의 루트 노드인 root를 입력으로 받고, 각 레벨에서 가장 큰 값들을 담은 벡터를 반환합니다.
입력 트리가 비어 있는 경우(root == nullptr), 빈 벡터를 반환합니다.

2. 변수 초기화

vector<int> ans;
queue<TreeNode*> queue;
queue.push(root);

ans: 결과를 저장할 벡터입니다. 각 트리 레벨의 최대값이 차례로 추가됩니다.
queue: BFS(너비 우선 탐색)를 위한 큐입니다. 루트 노드부터 탐색을 시작하기 위해 root를 큐에 추가합니다.

3. BFS를 통한 레벨 탐색

while (!queue.empty()) {

큐가 비어 있지 않은 동안 반복합니다. 각 반복은 트리의 한 레벨을 처리합니다.

a. 현재 레벨의 초기화

int currentLength = queue.size();
int currMax = INT_MIN;

currentLength: 현재 레벨의 노드 수입니다. 이는 현재 큐에 있는 노드 수로 계산됩니다.
currMax: 현재 레벨의 최대값을 저장할 변수입니다. 초기값은 가장 작은 정수(INT_MIN)로 설정됩니다.

b. 현재 레벨의 노드 처리

for (int i = 0; i < currentLength; i++) {
    TreeNode* node = queue.front();
    queue.pop();
    currMax = max(currMax, node->val);

반복문으로 현재 레벨의 모든 노드를 처리합니다.
queue.front()를 통해 큐의 맨 앞 노드를 가져오고, queue.pop()으로 큐에서 제거합니다.
노드의 값을 currMax와 비교하여 더 큰 값으로 갱신합니다.

c. 자식 노드 큐에 추가

    if (node->left) {
        queue.push(node->left);
    }

    if (node->right) {
        queue.push(node->right);
    }

현재 노드의 왼쪽(left) 자식과 오른쪽(right) 자식이 존재하면 각각 큐에 추가합니다. 이는 다음 레벨을 탐색하기 위해 준비하는 작업입니다.

4. 현재 레벨의 최대값 저장

ans.push_back(currMax);

현재 레벨에서 가장 큰 값(currMax)을 결과 벡터 ans에 추가합니다.

5. 결과 반환

return ans;

모든 레벨을 처리한 후, 결과 벡터를 반환합니다.

동작 과정 예시

입력 트리:

과정:

초기 상태:
- 큐: [1]
- ans: []
레벨 1:
- 큐에서 1을 처리. currMax = 1.
- 자식 노드 [3, 2] 큐에 추가.
- ans = [1].
레벨 2:
- 큐에서 3, 2 처리. currMax = 3.
- 자식 노드 [5, 3, 9] 큐에 추가.
- ans = [1, 3].
레벨 3:
- 큐에서 5, 3, 9 처리. currMax = 9.
- ans = [1, 3, 9].

시간 및 공간 복잡도

시간 복잡도:
- 각 노드를 한 번씩 방문하므로, 시간 복잡도는 $O(n)$ , 여기서 $n$ 은 노드의 개수입니다.
공간 복잡도:
- BFS 탐색을 위해 큐를 사용합니다. 최악의 경우, 큐에는 가장 많은 노드가 포함된 레벨(트리의 폭)만큼 노드가 저장됩니다. 따라서 공간 복잡도는 $O(w)$ , 여기서 $w$ 는 트리의 최대 폭입니다.

Approach 2: Depth First Search (DFS)

0ms, 22.74MB
Complexity
- Given $n$ as the number of nodes in the tree and $h$ as the max depth of the tree.
- Time Complexity: $O(n)$
- Space Complexity: $O(h)$

class Solution {
public:
    vector<int> ans;
    
    vector<int> largestValues(TreeNode* root) {
        dfs(root, 0);
        return ans;
    }
    
    void dfs(TreeNode* node, int depth) {
        if (node == nullptr) {
            return;
        }
        
        if (depth == ans.size()) {
            ans.push_back(node->val);
        } else {
            ans[depth] = max(ans[depth], node->val);
        }
        
        dfs(node->left, depth + 1);
        dfs(node->right, depth + 1);
    }
};

GPT

이 코드는 DFS(깊이 우선 탐색) 을 사용하여 이진 트리의 각 레벨에서 가장 큰 값을 찾는 알고리즘입니다. 이전 BFS 기반 코드와는 다른 방식으로 레벨별 최대값을 계산합니다. 이제 코드를 자세히 설명하겠습니다.

코드 분석

1. 클래스 멤버 초기화

vector<int> ans;

ans는 각 레벨의 최대값을 저장하는 벡터로, 클래스 멤버 변수로 선언됩니다.
DFS를 통해 재귀적으로 값을 계산하면서 업데이트됩니다.

2. `largestValues` 함수

vector<int> largestValues(TreeNode* root) {
    dfs(root, 0);
    return ans;
}

largestValues는 입력으로 받은 트리의 루트 노드(root)를 처리하며, 결과 벡터를 반환합니다.
내부적으로 재귀 함수 dfs를 호출하여 트리를 탐색합니다.
dfs 함수는 현재 노드와 노드의 깊이(depth)를 인자로 받습니다.

3. `dfs` 함수 (재귀 탐색)

void dfs(TreeNode* node, int depth) {
    if (node == nullptr) {
        return;
    }

이 함수는 깊이 우선 탐색(DFS)을 통해 트리를 탐색합니다.
노드가 nullptr인 경우, 즉 더 이상 탐색할 자식 노드가 없으면 반환합니다.

4. 현재 레벨의 최대값 갱신

if (depth == ans.size()) {
    ans.push_back(node->val);
} else {
    ans[depth] = max(ans[depth], node->val);
}

현재 깊이가 ans 벡터의 크기와 같다면:
- 이 레벨의 노드는 처음 방문한 것입니다.
- 현재 노드의 값을 ans에 추가합니다.
현재 깊이가 ans 벡터의 크기보다 작다면:
- 이미 이 레벨에서 다른 노드를 방문한 적이 있습니다.
- 기존 최대값(ans[depth])과 현재 노드 값(node->val) 중 더 큰 값을 저장합니다.

5. 재귀적으로 왼쪽 및 오른쪽 자식 탐색

dfs(node->left, depth + 1);
dfs(node->right, depth + 1);

왼쪽 자식과 오른쪽 자식을 재귀적으로 탐색하며, 깊이를 하나 증가시킵니다.

동작 과정 예시

입력 트리:

과정:

초기 상태:
- ans = [].
DFS 탐색 순서:
- 방문 순서: 1 → 3 → 5 → 3 → 2 → 9.
깊이에 따른 결과 갱신:
- 깊이 0: ans = [1] (노드 1 방문).
- 깊이 1: ans = [1, 3] (노드 3 방문).
- 깊이 2: ans = [1, 3, 5] (노드 5 방문).
- 깊이 2: ans = [1, 3, 5] (노드 3 방문, 최대값 유지).
- 깊이 1: ans = [1, 3] (노드 2 방문, 최대값 유지).
- 깊이 2: ans = [1, 3, 9] (노드 9 방문, 최대값 갱신).
최종 결과:
- ans = [1, 3, 9].

시간 및 공간 복잡도

시간 복잡도:

각 노드를 한 번씩 방문하므로 시간 복잡도는 $O(n)$ , 여기서 $n$ 은 노드의 개수입니다.

공간 복잡도:

DFS 재귀 호출은 트리의 깊이만큼 스택 공간을 사용합니다.
- 최악의 경우(트리가 편향된 경우), 스택 깊이는 $O(n)$ 입니다.
- 평균적으로 트리의 높이가 $h = O(\log n)$ 인 경우, 공간 복잡도는 $O(\log n)$ 입니다.
결과 벡터 ans의 공간 복잡도는 $O(d)$ , 여기서 $d$ 는 트리의 깊이입니다.

DFS vs BFS 비교

특징	DFS	BFS
탐색 방식	깊이를 우선 탐색 (재귀적)	레벨별 탐색 (큐 사용)
구현 난이도	재귀 함수로 간결하게 구현 가능	큐를 명시적으로 사용해야 함
공간 효율성	평균적으로 스택 공간 $O(\log n)$ 사용	큐 공간 $O(w)$ 필요 ( $w$ 는 트리의 최대 폭)
적용 상황	자연스럽게 레벨 정보 추적 가능	레벨 정보 명시적으로 관리해야 함

Approach 3: DFS, Iterative

0ms, 22.74MB
Complexity
- Given $n$ as the number of nodes in the tree and $h$ as the max depth of the tree.
- Time Complexity: $O(n)$
- Space Complexity: $O(h)$

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if (root == nullptr) {
            return vector<int>{};
        }
        
        vector<int> ans;
        stack<pair<TreeNode*, int>> stack;
        stack.push(make_pair(root, 0));
        
        while (!stack.empty()) {
            pair<TreeNode*, int> pair = stack.top();
            stack.pop();
            TreeNode* node = pair.first;
            int depth = pair.second;
            
            if (depth == ans.size()) {
                ans.push_back(node->val);
            } else {
                ans[depth] = max(ans[depth], node->val);
            }
            
            if (node->left) {
                stack.push(make_pair(node->left, depth + 1));
            }
            
            if (node->right) {
                stack.push(make_pair(node->right, depth + 1));
            }
        }
        
        return ans;
    }
};

GPT

이 코드는 DFS(깊이 우선 탐색) 을 사용하여 이진 트리의 각 레벨에서 최대값을 찾는 알고리즘입니다. 하지만 재귀 방식이 아닌 스택을 사용하는 반복적 구현입니다. 재귀 대신 스택을 활용하여 DFS를 수행하며, 각 노드의 깊이를 함께 관리합니다. 아래에서 코드의 주요 부분을 설명합니다.

코드 분석

1. 입력 트리의 초기 확인

if (root == nullptr) {
    return vector<int>{};
}

트리가 비어 있는 경우, 빈 벡터를 반환합니다.

2. 변수 초기화

vector<int> ans;
stack<pair<TreeNode*, int>> stack;
stack.push(make_pair(root, 0));

ans: 각 레벨의 최대값을 저장하는 벡터입니다.
stack: DFS를 수행하기 위한 스택입니다. 스택에는 노드(TreeNode*)와 해당 노드의 깊이(int)를 쌍(pair) 으로 저장합니다.
루트 노드와 깊이 0을 스택에 추가합니다.

3. DFS 탐색 루프

while (!stack.empty()) {

스택이 비어 있지 않은 동안 반복하여 트리를 탐색합니다.
각 반복은 스택에서 노드를 하나 꺼내 해당 노드와 그 깊이를 처리합니다.

4. 노드 및 깊이 처리

pair<TreeNode*, int> pair = stack.top();
stack.pop();
TreeNode* node = pair.first;
int depth = pair.second;

stack.top()으로 스택의 맨 위 요소(노드와 깊이의 쌍)를 가져옵니다.
stack.pop()으로 스택에서 해당 요소를 제거합니다.
node는 현재 탐색 중인 노드, depth는 해당 노드의 깊이입니다.

5. 현재 깊이의 최대값 갱신

if (depth == ans.size()) {
    ans.push_back(node->val);
} else {
    ans[depth] = max(ans[depth], node->val);
}

현재 깊이가 결과 벡터 ans의 크기와 같으면:
- 이 깊이에서 첫 번째로 방문한 노드이므로 node->val을 추가합니다.
현재 깊이가 결과 벡터 크기보다 작으면:
- 이미 이 깊이에서 다른 노드를 방문한 적이 있습니다.
- 기존 값과 현재 노드 값 중 더 큰 값을 저장합니다.

6. 자식 노드를 스택에 추가

if (node->left) {
    stack.push(make_pair(node->left, depth + 1));
}

if (node->right) {
    stack.push(make_pair(node->right, depth + 1));
}

왼쪽 자식과 오른쪽 자식이 존재하면 각각 스택에 추가하며, 깊이를 하나 증가시킵니다.
스택의 특징에 따라 오른쪽 자식을 먼저 추가합니다. 이렇게 하면 스택에서 꺼낼 때 왼쪽 자식을 먼저 처리하여 DFS의 왼쪽 우선 탐색 순서를 유지할 수 있습니다.

7. 결과 반환

return ans;

모든 노드를 처리한 후, 각 레벨의 최대값을 저장한 벡터 ans를 반환합니다.

동작 과정 예시

입력 트리:

과정:

초기 상태:
- 스택: [(1, 0)]
- ans = [].
DFS 탐색 순서 (스택의 변화):
- 스택에서 (1, 0) 꺼냄 → ans = [1] → 스택: [(3, 1), (2, 1)].
- 스택에서 (2, 1) 꺼냄 → ans = [1, 2] → 스택: [(3, 1), (9, 2)].
- 스택에서 (9, 2) 꺼냄 → ans = [1, 2, 9] → 스택: [(3, 1)].
- 스택에서 (3, 1) 꺼냄 → ans = [1, 3, 9] → 스택: [(5, 2), (3, 2)].
- 스택에서 (3, 2) 꺼냄 → ans = [1, 3, 9] → 스택: [(5, 2)].
- 스택에서 (5, 2) 꺼냄 → ans = [1, 3, 9] → 스택: [].
최종 결과:
- ans = [1, 3, 9].

시간 및 공간 복잡도

시간 복잡도:

각 노드를 한 번씩 방문하므로 시간 복잡도는 $O(n)$ , 여기서 $n$ 은 노드의 개수입니다.

공간 복잡도:

스택의 공간 복잡도는 트리의 높이 $h$ $h$ 에 비례합니다.
- 최악의 경우(트리가 편향된 경우), 공간 복잡도는 $O(n)$ .
- 평균적으로 트리가 균형 잡힌 경우, 공간 복잡도는 $O(\log n)$ .

DFS 스택 기반 구현 vs 재귀 구현

특징	스택 기반 DFS	재귀 기반 DFS
구현 복잡도	스택을 명시적으로 사용해야 함	재귀 호출로 간결하게 구현 가능
스택 오버플로우	스택 오버플로우 문제 없음	재귀 호출이 너무 깊어지면 스택 오버플로우 가능
유연성	깊이 및 추가 정보를 함께 관리하기 용이	추가 정보를 관리하려면 인자나 전역 변수 필요

515. Find Largest Value in Each Tree Row

내 코드

Solution

Approach 1: Breadth First Search (BFS)

GPT

코드 분석

1. 함수 정의와 초기 확인

2. 변수 초기화

3. BFS를 통한 레벨 탐색

a. 현재 레벨의 초기화

b. 현재 레벨의 노드 처리

c. 자식 노드 큐에 추가

4. 현재 레벨의 최대값 저장

5. 결과 반환

동작 과정 예시

입력 트리:

과정:

시간 및 공간 복잡도

Approach 2: Depth First Search (DFS)

GPT

코드 분석

1. 클래스 멤버 초기화

2. largestValues 함수

3. dfs 함수 (재귀 탐색)

4. 현재 레벨의 최대값 갱신

5. 재귀적으로 왼쪽 및 오른쪽 자식 탐색

동작 과정 예시

입력 트리:

과정:

시간 및 공간 복잡도

시간 복잡도:

공간 복잡도:

DFS vs BFS 비교

Approach 3: DFS, Iterative

GPT

코드 분석

1. 입력 트리의 초기 확인

2. 변수 초기화

3. DFS 탐색 루프

4. 노드 및 깊이 처리

5. 현재 깊이의 최대값 갱신

6. 자식 노드를 스택에 추가

7. 결과 반환

동작 과정 예시

입력 트리:

과정:

시간 및 공간 복잡도

시간 복잡도:

공간 복잡도:

DFS 스택 기반 구현 vs 재귀 구현

2. `largestValues` 함수

3. `dfs` 함수 (재귀 탐색)