题解 | #按之字形顺序打印二叉树#

方法一（BFS）

1.题意整理

• 给定一颗二叉树。
• 求二叉树的之字形遍历。之字形遍历是指第一层从左到右，第二层从右到左，一直这样交替。

2.思路整理

这题和二叉树的层序遍历非常相似，可以利用广度优先搜索来做。唯一不同的是，遇到偶数层的时候，需要对该层所有元素进行反转操作，然后再加入到结果集中。

• 首先新建一个队列，将根节点入队。
• 只要队列不为空，说明还可以继续遍历。当前队列大小即为当前层中节点个数。
• 每次遍历当前层所有节点，加入到临时list。遍历完之后加入到结果集。如果是偶数层，反转之后再加入到结果集。如果当前层节点的左右子节点不为空，则可以作为下一层节点加入到队列。

图解展示：

3.代码实现

import java.util.*;

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        //记录最终结果
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        //为空直接返回res
        if(pRoot==null) return res;
        //定义队列
        Queue<TreeNode> queue=new LinkedList<>();
        //将根节点加入队列
        queue.offer(pRoot);
        while(queue.size()>0){
            //当前层元素个数
            int n=queue.size();  
            ArrayList<Integer> list=new ArrayList<>();
            //遍历当前层所有元素
            for(int i=0;i<n;i++){
                //当前节点出队
                TreeNode node=queue.poll();
                //添加到list
                list.add(node.val);
                //如果有左右子节点，作为下一层加入队列
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //如果res大小为奇数，说明下一层是偶数层，需要反转之后再加入到res
            if(res.size()%2==1){
                Collections.reverse(list);
            }
            res.add(list);
        }
        return res;
    }

}

4.复杂度分析

• 时间复杂度：需要遍历二叉树中所有节点，每个节点进队和出队一次，然后偶数层元素需要反转，反转的元素个数不超过n，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：队列中元素的个数不超过n，所以空间复杂度为$O(n)O(n)$。