[数据结构与算法]NC14 按之字形顺序打印二叉树-Java

题目在这里
之字形打印二叉树，最容易想到的就是层次遍历了，以下是实现。

缺点

时间复杂度和空间复杂度都很高，不知道怎么优化。

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

/*
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 root) {
        ArrayList<ArrayList<Integer> > res = new ArrayList<>();
        if(root == null){
            return res;
        }
        
        LinkedList<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        boolean flag = true;
        TreeNode node = null;
        while(!q.isEmpty()){
            int size = q.size();
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                node = q.poll();
                if(node.left != null){
                    q.add(node.left);
                }
                if(node.right != null){
                    q.add(node.right);
                }
                if(flag){
                    list.add(node.val);
                }else{
                    list.add(0, node.val);
                }
                
            }
            res.add(list);
            flag = !flag;
        }
        return res;
    }

}