package com.hit.basmath.interview.top_interview_questions.medium_collection.trees_and_graphs;

import com.hit.common.TreeNode;

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

/**
 * 103. 二叉树的锯齿形层次遍历
 * <p>
 * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 * <p>
 * 例如：
 * <p>
 * 给定二叉树 [3,9,20,null,null,15,7],
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * <p>
 * 返回锯齿形层次遍历如下：
 * <p>
 * [
 * [3],
 * [20,9],
 * [15,7]
 * ]
 */
public class _103 {

    /**
     * 递归
     *
     * @param root 根节点
     * @return 遍历结果
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        helper(root, ans, 0);
        return ans;
    }

    private void helper(TreeNode node, List<List<Integer>> ans, int level) {
        if (node == null) return;
        if (ans.size() == level) {
            ans.add(new ArrayList<>());
        }
        List<Integer> collection = ans.get(level);
        if (level % 2 == 0) {
            collection.add(node.val);
        } else {
            collection.add(0, node.val);
        }
        helper(node.left, ans, level + 1);
        helper(node.right, ans, level + 1);
    }

    /**
     * 迭代
     *
     * @param root 根节点
     * @return 遍历结果
     */
    public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        LinkedList<TreeNode> nodeQueue = new LinkedList<>();
        nodeQueue.addLast(root);
        nodeQueue.addLast(null);
        LinkedList<Integer> levelList = new LinkedList<>();
        boolean isOrderLeft = true;
        while (nodeQueue.size() > 0) {
            TreeNode currNode = nodeQueue.pollFirst();
            if (currNode != null) {
                if (isOrderLeft) {
                    levelList.addLast(currNode.val);
                } else {
                    levelList.addFirst(currNode.val);
                }
                if (currNode.left != null) {
                    nodeQueue.addLast(currNode.left);
                }
                if (currNode.right != null) {
                    nodeQueue.addLast(currNode.right);
                }
            } else {
                ans.add(levelList);
                levelList = new LinkedList<>();
                if (nodeQueue.size() > 0) {
                    nodeQueue.addLast(null);
                }
                isOrderLeft = !isOrderLeft;
            }
        }
        return ans;
    }
}