[Codility] Tree Longest Zigzag

 

[Codility] Tree Longest Zigzag

 

https://app.codility.com/programmers/trainings/7/tree_longest_zig_zag/start/

Codility

---

 

해결전략

 

이진트리 Binary Tree

---

 

정답코드

 

#include <algorithm> 
using namespace std; 

int answer; // Longest Zigzag Length

void DFS(tree* node, int currLength, int dir) // 노드, 현재 경로의 길이, 진행 방향
{
    answer = max(answer, currLength); // 현재 경로의 길이와 이전까지의 최대 경로 길이 중 더 큰 값을 선택하여 저장

    // 만약 왼쪽 노드가 존재한다면
    if(node->l != nullptr){
        int newLength = currLength; // 새로운 경로의 길이를 현재 경로의 길이로 초기화

        if(dir == 1) newLength++; // 현재 진행 방향이 오른쪽(1)이라면 경로의 길이를 증가

        DFS(node->l, newLength, -1); // 새로운 길이와 왼쪽 노드로 DFS를 재귀적으로 호출. 이 때, 진행 방향은 왼쪽(-1).
    }

    // 만약 오른쪽 노드가 존재한다면
    if (node->r != nullptr){
        int newLength = currLength;

        if(dir == -1) newLength++; // 현재 진행 방향이 왼쪽(-1)이라면 경로의 길이를 증가

        DFS(node->r, newLength, 1); // 새로운 길이와 오른쪽 노드로 DFS를 재귀적으로 호출. 이 때, 진행 방향은 오른쪽(1).
    }
}

int solution(tree* T) {
    if(T == nullptr) return 0; // 트리가 비어 있다면 0을 반환.

    // 루트 노드에서 DFS를 시작. 이 때, 초기 경로의 길이는 0이며, 진행 방향은 없음(0)을 의미.
    DFS(T, 0, 0);

    return answer;
}

 

 

---