剑指 Offer 32 - I. 从上到下打印二叉树、剑指 Offer 32 - III. 从上到下打印二叉树 III

原题链接

class Solution {
    public int[] levelOrder(TreeNode root) {
        List list = new ArrayList<>();
        if(root == null) return new int[0];
        LinkedList que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int len = que.size();
            while(len > 0){
                TreeNode node = que.poll();
                list.add(node.val);
                if(node.left != null) que.offer(node.left);
                if(node.right != null) que.offer(node.right);
                len--;
            }
        }
        int[] res = new int[list.size()];
        int index = 0;
        for(int x : list){
            res[index++] = x;
        }
        return res;
    }
}

原题链接

1. 此题要求有的层顺序有的层逆序
2. 用来记录每层的item 是使用 LinkedList 类型的双向链表，而不是普通的 List
3. 使用res.size() % 2 来判断当前层是奇数还是偶数，偶数则 item.addLast () 奇数层则 item.addFirst

class Solution {
    public List> levelOrder(TreeNode root) {
        List> res = new ArrayList<>();
        if(root == null) return res;
        Deque que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int len = que.size();
            LinkedList item = new LinkedList<>();
            while(len > 0){
                TreeNode node = que.poll();
                if((res.size() % 2) == 0) item.addLast(node.val);
                else{
                    item.addFirst(node.val);
                }
                if(node.left != null) que.offer(node.left);
                if(node.right != null) que.offer(node.right);
                len--;
            }
            res.add(item);
        }
        return res;
    }
}