package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.sql.Struct;

/**
 * 1372. Longest ZigZag Path in a Binary Tree
 *
 * Given a binary tree root, 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 then move to the right child of the current node otherwise move to the left child.
 * Change the direction from right to left or right to left.
 * Repeat the second and third step 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.
 *
 * Example 1:
 * Input: root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
 * Output: 3
 * Explanation: Longest ZigZag path in blue nodes (right -> left -> right).
 *
 * Example 2:
 * Input: root = [1,1,1,null,1,null,null,1,1,null,1]
 * Output: 4
 * Explanation: Longest ZigZag path in blue nodes (left -> right -> left -> right).
 *
 * Example 3:
 * Input: root = [1]
 * Output: 0
 *
 * Constraints:
 * Each tree has at most 50000 nodes..
 * Each node's value is between [1, 100].
 * */
public class _1372 {
    public static class Solution1 {
        /**credit: https://leetcode.com/problems/longest-zigzag-path-in-a-binary-tree/discuss/531808/Java-Recursion-Try-each-node-as-a-zigzag-root-then-return-valid-sum-to-parent*/
        int maxLength = 0;

        public int longestZigZag(TreeNode root) {
            dfs(root, true);
            return maxLength;
        }

        private int dfs(TreeNode root, boolean isLeft) {
            if (root == null) {
                return 0;
            }
            int left = dfs(root.left, false);
            int right = dfs(root.right, true);
            maxLength = Math.max(maxLength, left);
            maxLength = Math.max(maxLength, right);
            return 1 + (isLeft ? left : right);
        }
    }
}

@@ -107,1130 +107,8 @@
 t;%0A%0A
-/**%0A * 1372. Longest ZigZag Path in a Binary Tree%0A *%0A * Given a binary tree root, a ZigZag path for a binary tree is defined as follow:%0A * Choose any node in the binary tree and a direction (right or left).%0A * If the current direction is right then move to the right child of the current node otherwise move to the left child.%0A * Change the direction from right to left or right to left.%0A * Repeat the second and third step until you can't move in the tree.%0A * Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).%0A * Return the longest ZigZag path contained in that tree.%0A *%0A * Example 1:%0A * Input: root = %5B1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1%5D%0A * Output: 3%0A * Explanation: Longest ZigZag path in blue nodes (right -%3E left -%3E right).%0A *%0A * Example 2:%0A * Input: root = %5B1,1,1,null,1,null,null,1,1,null,1%5D%0A * Output: 4%0A * Explanation: Longest ZigZag path in blue nodes (left -%3E right -%3E left -%3E right).%0A *%0A * Example 3:%0A * Input: root = %5B1%5D%0A * Output: 0%0A *%0A * Constraints:%0A * Each tree has at most 50000 nodes..%0A * Each node's value is between %5B1, 100%5D.%0A * */%0A
 publ
@@ -171,16 +171,28 @@
      /**
+%0A         * 
 credit: 
@@ -350,16 +350,26 @@
 o-parent
+%0A         
 */%0A     

refactor 1372