C++로 풀어보는 이진 트리의 가장 긴 지그재그(ZigZag) 경로

이진 트리의 루트 노드가 주어졌을 때, 지그재그(ZigZag) 경로는 다음과 같이 정의됩니다.

이진 트리에서 임의의 노드 하나와 방향(오른쪽 또는 왼쪽)을 선택합니다.
현재 방향이 오른쪽이라면 현재 노드의 오른쪽 자식으로 이동하고, 그렇지 않다면 왼쪽 자식으로 이동합니다.
이동 후에는 방향을 오른쪽에서 왼쪽으로, 또는 왼쪽에서 오른쪽으로 전환합니다.
트리에서 더 이상 이동할 수 없을 때까지 두 번째와 세 번째 단계를 반복합니다.

지그재그 경로의 길이는 방문한 노드 수에서 1을 뺀 값으로 정의됩니다. 즉, 노드가 하나만 있는 경우 길이는 0입니다. 우리의 목표는 트리에 포함된 가장 긴 지그재그 경로를 찾는 것입니다.

예를 들어, 아래와 같은 트리가 주어졌다고 가정해 보겠습니다.

이 경우 출력은 3이며, 이는 (오른쪽 → 왼쪽 → 오른쪽) 순서로 진행되는 경로에 해당합니다.

문제 해결 접근 방법

이 문제는 깊이 우선 탐색(DFS)을 활용하면 효율적으로 해결할 수 있습니다. 각 노드에서 왼쪽과 오른쪽 방향으로 시작하는 지그재그 경로의 길이를 재귀적으로 계산하면서 최댓값을 갱신하는 방식입니다. 구체적인 단계는 다음과 같습니다.

루트 노드와 방향 플래그(leftB)를 매개변수로 받는 dfs() 메서드를 정의합니다.
루트가 null이면 -1을 반환합니다.
루트가 리프 노드(자식이 없는 유일한 노드)라면 0을 반환합니다.
leftV := dfs(루트의 왼쪽 자식, true), rightV := dfs(루트의 오른쪽 자식, false)로 재귀 호출합니다.
ret := max(ret, 1 + max(leftV, rightV))로 결과값을 갱신합니다.
leftB가 true이면 1 + rightV를 반환하고, 그렇지 않으면 1 + leftV를 반환합니다.
메인 메서드에서 ret := 0으로 초기화합니다.
dfs(root, true)와 dfs(root, false)를 차례로 호출합니다.
ret을 반환합니다.

이 알고리즘은 모든 노드를 한 번씩만 방문하므로 시간 복잡도는 O(n)입니다. 여기서 n은 트리의 노드 개수입니다.

C++ 구현 예시

아래 구현 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
    public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = right = NULL;
    }
};
void insert(TreeNode **root, int val){
    queue<TreeNode*> q;
    q.push(*root);
    while(q.size()){
        TreeNode *temp = q.front();
        q.pop();
        if(!temp->left){
            if(val != NULL)
                temp->left = new TreeNode(val);
            else
                temp->left = new TreeNode(0);
            return;
        } else {
            q.push(temp->left);
        }
        if(!temp->right){
            if(val != NULL)
                temp->right = new TreeNode(val);
            else
                temp->right = new TreeNode(0);
            return;
        }else{
            q.push(temp->right);
        }
    }
}
TreeNode *make_tree(vector<int> v){
    TreeNode *root = new TreeNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        insert(&root, v[i]);
    }
    return root;
}
class Solution {
    public:
    int ret;
    int dfs(TreeNode* root, bool leftB){
        if(!root) return -1;
        if(!root->left && !root->right) return 0;
        int leftV = dfs(root->left, true);
        int rightV = dfs(root->right, false);
        ret = max(ret, 1 + max(leftV, rightV));
        if(leftB) return 1 + rightV;
        return 1 + leftV;
    }
    int longestZigZag(TreeNode* root) {
        ret = 0;
        dfs(root, true);
        dfs(root, false);
        return ret;
    }
};
main(){
    vector<int> v = {1,NULL,1,1,1,NULL,NULL,1,1,NULL,1,NULL,NULL,NULL,1,NULL,1};
    TreeNode *root = make_tree(v);
    Solution ob;
    cout << (ob.longestZigZag(root));
}

입력

[1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]