题目

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如: 给定二叉树: [3,9,20,null,null,15,7]

  3

 / \

9  20

    /  \

    15   7

返回其层次遍历结果：

[ [3], [20,9], [15,7] ]

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof

解题思路

使用一个队列存储每一层的节点，level变量记录第几层，初始level等于1, 每次循环都记录下当前队列的大小（n）,n即为每层的节点数量，当队列不为空时， 每次出队n个节点同时保存节点的值到一个list（当level为偶数时使用链表头插法）， 每层节点遍历完后level+1,直到队列为空，最后返回结果

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>>  res =new ArrayList<>();
        if(root == null) return res;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int level=1;
        while(!queue.isEmpty()){
            List<Integer> tmp=new ArrayList<>();
            int n=queue.size();
            for(int i=0;i<n;i++){
                TreeNode node=queue.poll();
                if((level & 1)==1){
                    tmp.add(node.val);
                }else{
                    tmp.add(0,node.val);//头插法
                }
                if(node.left !=null) queue.offer(node.left);
                if(node.right !=null) queue.offer(node.right);
            }
            level++;
            res.add(tmp);

        }
        return res;
    }
}