Longest ZigZag Path in a Binary Tree

1package pkg5leetcode.official75;2 3/*4 * Longest ZigZag Path in a Binary Tree | LC 13725 * APPROACH: DFS track length by direction left/right.6 * COMPLEXITY: Time O(n), Space O(h)7 */8public class official75_LC1372LongestZigZagPathInBinaryTree {9    /** Same shape as pkg5leetcode/common/TreeNode.java (nested for single-file runs). */10 11    static class TreeNode {12        int val;13        TreeNode left, right;14        TreeNode(int val) { this.val = val; }15    }16 17    static int best = 0;18 19    static int longestZigZag(TreeNode root) {20        best = 0;21        dfs(root);22        return best;23    }24 25    static int[] dfs(TreeNode node) {26        if (node == null) return new int[]{0, 0};27        int[] L = dfs(node.left), R = dfs(node.right);28        int left = 1 + L[1], right = 1 + R[0];29        best = Math.max(best, Math.max(left, right));30        return new int[]{left, right};31    }32 33    public static void main(String[] args) {34        TreeNode root = new TreeNode(1);35        root.right = new TreeNode(1); root.right.left = new TreeNode(1);36        root.right.right = new TreeNode(1); root.right.right.left = new TreeNode(1);37        root.right.right.right = new TreeNode(1); root.right.right.right.left = new TreeNode(1);38        root.right.right.right.right = new TreeNode(1);39        check(longestZigZag(root) == 3, "case1");40        TreeNode r2 = new TreeNode(1); r2.left = new TreeNode(1); r2.right = new TreeNode(1);41        r2.left.right = new TreeNode(1); r2.left.right.right = new TreeNode(1);42        r2.left.right.right.right = new TreeNode(1); r2.left.right.right.right.right = new TreeNode(1);43        check(longestZigZag(r2) == 3, "case2");44        System.out.println("all tests passed");45    }46 47    static void check(boolean cond, String name) {48        if (!cond) throw new AssertionError("FAILED: " + name);49        System.out.println("  PASS " + name);50    }51}