/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    // 层序遍历 (遍历树)
    public String serialize(TreeNode root) {
        if (root == null) return "[]";
        String string = "[";
        Deque<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int cnt = 0;
        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            if (cnt != 0) string += ",";
            if (node == null) {
                string += "null";
            } else {
                string += String.valueOf(node.val);
                que.offer(node.left);
                que.offer(node.right);
            }
            cnt ++;
        }
        string += "]";
        return string;
    }

    // Decodes your encoded data to tree.
    // 建树
    public TreeNode deserialize(String data) {
        data = data.trim(); // 去除首尾两端多余的空格
        data = data.substring(1, data.length() - 1);    // 去除首尾两端的'['、']'
        if ("null".equals(data) || data.length() == 0) return null;    // []
        String[] strings = data.split(",");
        TreeNode dummy = new TreeNode(-1);  // 哑节点
        TreeNode prev = dummy;

        Deque<TreeNode> que = new LinkedList<>();
        int idx = 0;
        TreeNode root = new TreeNode(Integer.parseInt(strings[idx++]));
        dummy.left = root;
        que.offer(root);
        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            if ("null".equals(strings[idx])) {
                node.left = null;
            } else {
                node.left = new TreeNode(Integer.parseInt(strings[idx]));
                que.offer(node.left);
            }
            idx++;
            if ("null".equals(strings[idx])) {
                node.right = null;
            } else {
                node.right = new TreeNode(Integer.parseInt(strings[idx]));
                que.offer(node.right);
            }
            idx++;
        }

        return dummy.left;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

// 二叉树的序列化和反序列化考察的是：二叉树的建树和输出的过程，必须记住

  * 方法二：
  * 使用dfs进行搜索，用map记录每层最后遍历到的节点
  * 偶数下标 层上的所有节点的值都是 奇 整数，从左到右按顺序 严格递增
  * 奇数下标 层上的所有节点的值都是 偶 整数，从左到右按顺序 严格递减
  */
class Solution {
    Map<Integer, Integer> map = new HashMap<>();    // <每层序号， 每一层的最后节点>
    public boolean isEvenOddTree(TreeNode root) {
        return dfs(root, 0);
    }

    public boolean dfs(TreeNode node, int index) {
        boolean flag = index % 2 == 0? true: false;
        int prev = map.getOrDefault(index, flag? 0: 0x3f3f3f3f);
        int curr = node.val;
        if (flag && (curr % 2 == 0 || curr <= prev)) return false;
        if (!flag && (curr % 2 == 1 || curr >= prev)) return false;
        map.put(index, node.val);
        if (node.left != null && !dfs(node.left, index + 1)) return false;
        if (node.right != null && !dfs(node.right, index + 1)) return false;

        return true; 
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
 /**
  * 偶数下标为奇函数，严格递增
  * 奇数下标为偶函数，严格递减
  * 层序遍历
  */
class Solution {
    public boolean isEvenOddTree(TreeNode root) {
        Deque<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int level = 0;
        while (!que.isEmpty()) {
            int size = que.size();
            TreeNode prev = null;
            for (int i = 0; i < size; i++) {
                TreeNode curr = que.poll();
                if (level % 2 == 0) {
                    if (curr.val % 2 != 1) return false;
                    if (prev != null && curr.val <= prev.val) return false;                    
                } else {
                    if (curr.val % 2 != 0) return false;
                    if (prev != null && curr.val >= prev.val) return false;    
                }
                prev = curr;
                if (curr.left != null) que.offer(curr.left);
                if (curr.right != null) que.offer(curr.right);
            }
            level++;
        }

        return true;
    }
}