23.04.19. 풀었던 문제들

Leetcode 1372. Longest ZigZag Path in a Binary Tree

 어떤 binary tree가 주어졌을 때, zigzag로 탐색한 가장 긴 path length를 찾는 문제. 여기서 zigzag는 왼쪽 - 오른쪽 - 왼쪽 - ... , 또는 오른쪽 - 왼쪽 - 오른쪽 - ... 와 같이 [이전에 탐색한 방향]과 [이번에 탐색한 방향]이 다른 경우로 정의한다.

 dfs를 하면서 top-down으로, 그러니까 parent의 값을 child에 넣고, 탐색 종료 시 정답을 갱신하는 방식이 아니라 child의 값을 parent로 끌어올리면서 정답을 계산해야 하는 문제 같다.정확하게 문제는 기억나질 않는데, 프로그래머스에서 이런 유형의 문제를 풀었던 것 같다.

 

 일단 해설하자면, root부터 시작해서, DFS 결과로 [현 vertex의 left로 시작하는 zigzag max length, 현 vertex의 right부터 시작하는 zigzag max length]를 리턴한다고 하자. first를 [현 vertex의 left로 시작하는 zigzag max length], second를 [현 vertex의 right부터 시작하는 zigzag max length]라고 두겠다.

 

 그러면, 현재 vertex에서 왼쪽부터 zigzag를 시작하는 경우 아래 2가지 경우의 수가 존재한다.

• left child에서 계속 zigzag 탐색을 이어가는 경우 (cur->left->right->left->right->...)
• 또는 left child에서 left부터 시작하는 zigzag path length가 가장 큰 경우 (cur->left->left->right->...)

 첫 번째 경우는 현 vertex에서 왼쪽으로 한 번 진행한 상태이므로 다음 진행 방향은 무조건 오른쪽이 되어야 한다. 따라서 cur->left의 second + 1. 두 번째 경우는 cur->left의 first.

 

 현 vertex에서 오른쪽부터 zigzag를 시작하는 경우도 마찬가지.

• right child에서 계속 zigzag 탐색을 이어가는 경우 (cur->right->left->right->...)
• 또는 right child에서 right부터 시작하는 zigzag path length가 가장 긴 경우(cur->right->right->left->right->...)

 첫 번째 경우는 현 vertex에서 오른쪽으로 한 번 진행한 상태이므로 다음 진행 방향은 무조건 왼쪽이 되어야 한다. 따라서 cur->right의 first + 1, 두 번째 경우는 마찬가지로 cur->right의 second.

 

 이 때, 현재 vertex부터 왼쪽으로 탐색하든 오른쪽으로 탐색하든 그 max path를 항상 answer에 저장한다.

 

// Runtime 184 ms Beats 41.81%
// Memory 103.2 MB Beats 33.45%

typedef pair<int, int> pii;
class Solution {
public:
    int answer = 0;
    pii dfs(TreeNode* cur){
        int leftlen = 0, rightlen = 0;
        if(cur->left){
            pii leftResult = dfs(cur->left);
            leftlen = max(leftlen, leftResult.second + 1);
            answer = max(answer, max(leftResult.first, leftResult.second + 1));
        }
        if(cur->right){
            pii rightResult = dfs(cur->right);
            rightlen = max(rightlen, rightResult.first + 1);
            answer = max(answer, max(rightResult.first + 1, rightResult.second));
        }
        return {leftlen, rightlen};
    }
    int longestZigZag(TreeNode* root) {
        pii result = dfs(root);
        return answer;
    }
};

/**
 * 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) {}
 * };
 */

 

시간복잡도

 DFS 한 번이므로 O(V+E), E = 2V이므로 O(V)

 

공간복잡도

 worst case tree height만큼 stack이 쌓이므로 O(H), 이는 worst case O(V)이다. 따라서 O(V)

 

후기

 오랜만에 생각을 좀 해야 하는 문제가 나왔다. 이런 문제 + 좀 더 어려운 문제들만 좀 나왔으면... 너무 쉬운 문제는 솔직히 시간낭비같다.