leetcode link

Description

You are given the root of a binary tree.

A ZigZag path for a binary tree is defined as follow:

• Choose any node in the binary tree and a direction (right or left).
• If the current direction is right, move to the right child of the current node; otherwise, move to the left child.
• Change the direction from right to left or from left to right.
• Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

---

1372. 이진 트리에서 가장 긴 지그재그 경로

이진 트리의 root가 주어집니다.

이진 트리에 대한 지그재그 경로는 다음과 같이 정의됩니다:

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

지그재그 길이는 방문한 노드의 수 - 1로 정의됩니다. (단일 노드의 길이는 0입니다).

해당 트리에 포함된 가장 긴 지그재그 경로를 반환하세요.

예제 1:

입력: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1]
출력: 3
설명: 파란 노드에서의 가장 긴 지그재그 경로 (오른쪽 -> 왼쪽 -> 오른쪽).

예제 2:

입력: root = [1,1,1,null,1,null,null,1,1,null,1]
출력: 4
설명: 파란 노드에서의 가장 긴 지그재그 경로 (왼쪽 -> 오른쪽 -> 왼쪽 -> 오른쪽).

예제 3:

입력: root = [1]
출력: 0

제약 조건:

• 트리의 노드 수는 [1, 5 * 10^4] 범위에 있습니다.
• 1 <= Node.val <= 100

Solution

class Solution {
    // 가장 긴 지그재그 경로의 길이 저장
    int longestZigZagLength = 0;

    public int longestZigZag(TreeNode root) {
        dfs(root.left, Direction.LEFT, 0);
        dfs(root.right, Direction.RIGHT, 0);
        return longestZigZagLength; // 최장 경로 길이 반환
    }

    enum Direction { // 탐색 방향
        LEFT, RIGHT
    }

    void dfs(TreeNode node, Direction direction, int currentLength) {
        if (node == null) {
            longestZigZagLength = Math.max(longestZigZagLength, currentLength); // 최대 길이 업데이트
            return;
        }
        // 왼쪽 또는 오른쪽으로 이동 시 방향 변경 및 경로 길이 계산
        if (direction == Direction.LEFT) {
            dfs(node.right, Direction.RIGHT, currentLength + 1); // 왼쪽에서 오른쪽으로 이동
            dfs(node.left, Direction.LEFT, 0); // 경로 리셋
        } else {
            dfs(node.left, Direction.LEFT, currentLength + 1); // 오른쪽에서 왼쪽으로 이동
            dfs(node.right, Direction.RIGHT, 0); // 경로 리셋
        }
    }
}