/**

 * 从上往下打印出二叉树的每个节点，同层节点从左至右打印。

 * Created by YuKai Fan on 2018/9/8.

 */

public class PrintTreeFromTopBottom {

    public static void main(String[] args) {

        TreeNode a = new TreeNode(2);

        a.left = new TreeNode(4);

        a.right = new TreeNode(6);

        a.left.left = new TreeNode(7);

        a.left.right = new TreeNode(9);

        a.right.right = new TreeNode(21);

        a.right.left = new TreeNode(14);

        ArrayList<Integer> list = printTreeFromTopBottom(a);

        System.out.println(list);

    }

    /*

    思路是用arraylist模拟一个队列来存储相应的TreeNode,每次遍历将树的左节点，和右节点放入队列中

     */

    public static ArrayList<Integer> printTreeFromTopBottom(TreeNode root) {

        ArrayList<Integer> list = new ArrayList<>();

        ArrayList<TreeNode> queue = new ArrayList<>();

        if (root == null) {

            return list;

        }

        queue.add(root);

        while (queue.size() != 0) {

            TreeNode temp = queue.remove(0);

            if (temp.left != null) {

                queue.add(temp.left);

            }

            if (temp.right != null) {

                queue.add(temp.right);

            }

            list.add(temp.val);

        }

        return list;

    }

}

/**

 * Created by YuKai Fan on 2018/9/3.

 */

public class TreeNode {

    int val;

    TreeNode left;

    TreeNode right;

    TreeNode(int val) {

        this.val = val;

    }

}

/*

    从上往下打印“之字形”二叉树

     */

    public static ArrayList<ArrayList<Integer>> printTreeFromTopBottom2(TreeNode root) {

        //result用来存储结果

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        //创建两个辅助栈，分别存放奇数行和偶数行的节点

        Stack<TreeNode> stack1 = new Stack<>();

        Stack<TreeNode> stack2 = new Stack<>();

        //创建集合，存放每一行的节点值

        ArrayList<Integer> list = new ArrayList<>();

        boolean flag = true;

        TreeNode node;

        stack1.push(root);

        while (!stack1.isEmpty() || !stack2.isEmpty()) {

            //奇数行，从左往右入栈stack2

            if (flag) {

                while (!stack1.isEmpty()) {

                    node = stack1.pop();

                    list.add(node.val);

                    if (node.left != null) {

                        stack2.push(node.left);

                    }

                    if (node.right != null) {

                        stack2.push(node.right);

                    }

                    if (stack1.isEmpty()) {

                        result.add(list);

                        list = new ArrayList<>();

                    }

                }

            } else {

                //偶数行，将入栈的奇数行出栈到stack1

                while (!stack2.isEmpty()) {

                    node = stack2.pop();//由于后进先出，所以弹出的是右子树

                    list.add(node.val);//将右节点存入

                    if (node.right != null) {

                        stack1.push(node.right);

                    }

                    if (node.left != null) {

                        stack1.push(node.left);

                    }

                    if (stack2.isEmpty()) {

                        result.add(list);

                        list = new ArrayList<>();

                    }

                }

            }

            flag = !flag;

        }

        return result;

    }