[Binary Tree - DFS, Medium] Longest ZigZag Path in a Binary Tree

https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/description/?envType=study-plan-v2&envId=leetcode-75

방향에 대한 인자를 받아서 역방향으로 dfs 순회하면 지그재그는 쉽게 찾을 수 있다.
그러나 문제 이해를 잘 못해서 same direction 여러 케이스들을 맞추느라 좀 헤맸는데,

같은 방향으로밖에 못 가는 경우는 지그재그가 아니기 때문에 다시 초기화인가보더라.

지그재그 path - 1값이 정답 범위이기 때문에 처음 dfs 순회는
root.left, root.right 로 depth 0으로 시작했다.

왼쪽으로 시작한 값과 오른쪽으로 시작한 값 중 Math.max해서 높은 값을 리턴한다.

dfs 메서드 로직 자체는 단순한데,
중요한 것은 각 방향마다 지그재그로 갈 수 없어서 초기화되는 케이스도 고려해야 한다는 점이다.

class Solution {

    public int longestZigZag(TreeNode root) {
        int leftStart = dfs(root.left, 0, false);
        int rightStart = dfs(root.right, 0, true);

        return Math.max(leftStart, rightStart);
    }

    public int dfs(TreeNode node, int depth, boolean toLeft) {
        if (node == null) {
            return depth;
        }

        if (toLeft) {
            int directionChanged = dfs(node.left, depth + 1, false);
            int sameDirection = dfs(node.right, 0, true); // 같은 방향이면 초기화
            return Math.max(directionChanged, sameDirection);
        } else {
            int directionChanged = dfs(node.right, depth + 1, true);
            int sameDirection = dfs(node.left, 0, false); // 같은 방향이면 초기화
            return Math.max(directionChanged, sameDirection);
        }
    }
}