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) {
        IntRef answer = new IntRef();
        longestZigZag(root, answer);
        return answer.val;
    }

    private static void longestZigZag(TreeNode root, IntRef ref) {
        if (root == null) {
            return;
        }
        longestZigZag(root.left, ref);
        longestZigZag(root.right, ref);
        ref.val = Math.max(ref.val, Math.max(
            longestZigZag(root, Direction.LEFT),
            longestZigZag(root, Direction.RIGHT)) - 1);
    }

    private static class IntRef {
        private int val;
    }

    private enum Direction {
        LEFT, RIGHT
    }

    private static int longestZigZag(TreeNode root, Direction direction) {
        if (root == null) {
            return 0;
        }
        if (direction == Direction.LEFT) {
            return longestZigZag(root.left, Direction.RIGHT) + 1;
        }
        return longestZigZag(root.right, Direction.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
    }
}

@@ -428,16 +428,20 @@
 swer.val
+ - 1
 ;%0A    %7D%0A
@@ -464,53 +464,20 @@
 tic 
-void longestZigZag(TreeNode root,
+class
  IntRef
- ref)
  %7B%0A 
@@ -487,135 +487,89 @@
     
-if (root == null) %7B%0A            return
+private int val
 ;%0A    
-    
 %7D%0A
- 
+%0A
     
-   longestZigZag(root.left, ref);%0A        longestZigZag(root.right, ref)
+private static class Count %7B%0A        private int left
 ;%0A  
@@ -578,272 +578,143 @@
     
-ref.val = Math.max(ref.val, Math.max(%0A            longestZigZag(root, Direction.LEFT),%0A            longestZigZag(root, Direction.RIGHT)) - 1)
+private int right;%0A%0A        public Count(int left, int right) %7B%0A            this.left = left
 ;%0A    
-%7D%0A%0A
     
-private static class IntRef %7B%0A        private int val;%0A    %7D%0A%0A    private enum Direction %7B%0A        LEFT, RIGHT
+    this.right = right;%0A        %7D
 %0A   
@@ -736,17 +736,19 @@
  static 
-i
+Cou
 nt longe
@@ -775,27 +775,18 @@
 ot, 
-Direction direction
+IntRef max
 ) %7B%0A
@@ -836,9 +836,23 @@
 urn 
-0
+new Count(0, 0)
 ;%0A  
@@ -871,133 +871,73 @@
     
-if (direction == Direction.LEFT) %7B%0A            return longestZigZag(root.left, Direction.RIGHT) + 1;%0A        %7D%0A        return
+Count left = longestZigZag(root.left, max);%0A        Count right =
  lon
@@ -963,567 +963,213 @@
 ht, 
-Direction.LEFT) + 1
+max)
 ;%0A    
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem1372 prob = new Problem1372();%0A%0A        TreeNode root = new TreeNode(1);%0A        root.right = new TreeNode(1);%0A        root.right.left = new TreeNode(1);%0A        root.right.right = new TreeNode(1);%0A        root.right.right.left = new TreeNode(1);%0A        root.right.right.right = new TreeNode(1);%0A        root.right.right.left.right = new TreeNode(1);%0A        root.right.right.left.right.right = new TreeNode(1);%0A        System.out.println(prob.longestZigZag(root)); // 3
+int leftCount = left.right + 1;%0A        int rightCount = right.left + 1;%0A        max.val = Math.max(max.val, Math.max(leftCount, rightCount));%0A        return new Count(leftCount, rightCount);
 %0A   

Solve problem 1372