package leetcode;

/**
 * https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/
 */
public class Problem1372 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public int longestZigZag(TreeNode root) {
        return Math.max(longestZigZag(root, true), longestZigZag(root, false)) - 1;
    }

    private static int longestZigZag(TreeNode root, boolean left) {
        if (root == null) {
            return 0;
        }
        if (left) {
            return longestZigZag(root.left, !left) + 1;
        }
        return longestZigZag(root.right, !left) + 1;
    }

    public static void main(String[] args) {
        Problem1372 prob = new Problem1372();

        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(1);
        root.right.left = new TreeNode(1);
        root.right.right = new TreeNode(1);
        root.right.right.left = new TreeNode(1);
        root.right.right.right = new TreeNode(1);
        root.right.right.left.right = new TreeNode(1);
        root.right.right.left.right.right = new TreeNode(1);
        System.out.println(prob.longestZigZag(root)); // 3
    }
}

@@ -340,50 +340,419 @@
     
-return Math.max(longestZigZag(root, true),
+IntRef answer = new IntRef();%0A        longestZigZag(root, answer);%0A        return answer.val;%0A    %7D%0A%0A    private static void longestZigZag(TreeNode root, IntRef ref) %7B%0A        if (root == null) %7B%0A            return;%0A        %7D%0A        longestZigZag(root.left, ref);%0A        longestZigZag(root.right, ref);%0A        ref.val = Math.max(ref.val, Math.max(%0A            longestZigZag(root, Direction.LEFT),%0A           
  lon
@@ -772,19 +772,30 @@
 ot, 
-false
+Direction.RIGHT
 )) - 1
+)
 ;%0A  
@@ -791,32 +791,154 @@
 )) - 1);%0A    %7D%0A%0A
+    private static class IntRef %7B%0A        private int val;%0A    %7D%0A%0A    private enum Direction %7B%0A        LEFT, RIGHT%0A    %7D%0A%0A
     private stat
@@ -977,20 +977,27 @@
 ot, 
-boolean left
+Direction direction
 ) %7B%0A
@@ -1068,20 +1068,43 @@
     if (
-left
+direction == Direction.LEFT
 ) %7B%0A    
@@ -1143,21 +1143,31 @@
 t.left, 
-!left
+Direction.RIGHT
 ) + 1;%0A 
@@ -1220,13 +1220,22 @@
 ht, 
-!left
+Direction.LEFT
 ) + 

Update problem 1372