package com.company. 二叉树 ;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 二叉树数的Z字型遍历 {

    /**
     * 内部类
     */
    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;
        }
    }
    /**
     * 广度优先解法
     * 思路分析：
     * 第一步：先进行边界值判断
     * 第二步：创建一个队列，入队根节点
     * 第三步：whlile循环出队
     * 第四步：重点：每次出队的时候会把左右节点进行入队，可以理解为入队了第二层的所有的节点，
     *  第二层出队时，把所有的节点拿出来之后，放入list中，然后把所有第二层节点的左右节点入队，
     *  这个地方要注意Z型遍历时，规律是偶数是从左到右，奇数是从右到左，
     *  所以用取余数来判断增加节点的数序, 然后就是第三层,依次循环处理，注意边界值的判断，
     *  如果是空的话就不用放入list中, 第五步：依次按循环的list增加到全局的list中返回。
     * @param root
     * @return
     */
    public List<List<Integer>> zLevelOrder(TreeNode root) {
        List<List< Integer >> list = new ArrayList<>();
        if (root == null) return list;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> res = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                res.add(node.val);
                if (i%2 == 0) {
                    if (root.left != null) {
                        queue.offer(root.left);
                    }
                    if (root.right != null) {
                        queue.offer(root.right);
                    }
                } else {
                    if (root.right != null) {
                        queue.offer(root.right);
                    }
                    if (root.left != null) {
                        queue.offer(root.left);
                    }
                }

            }
            list.add(res);
        }
        return list;
    }
}