之字形打印二叉树

请实现一个函数按照之字形顺序从上向下打印二叉树。

即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

样例 输入如下图所示二叉树[8, 12, 2, null, null, 6, 4, null, null, null, null] 8 / \ 12 2 / \ 6 4 输出：[[8], [2, 12], [6, 4]]

BFS

时间复杂度O(n)

class Solution { public List<List<Integer>> printFromTopToBottom(TreeNode root) { List<List<Integer>> ras = new ArrayList<>(); if(root==null) return ras; Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); boolean flag = true; while(!queue.isEmpty()){ int size = queue.size(); List<Integer> curList = new LinkedList<>(); for(int i = 0;i < size;i++){ TreeNode node = queue.poll(); if(flag){ curList.add(node.val); }else{ curList.add(0,node.val); } if(node.left != null){ queue.add(node.left); } if(node.right != null){ queue.add(node.right); } } flag = !flag; ras.add(curList); } return ras; } }