32 从上往下打印二叉树

题目一：从上往下打印二叉树

牛客

使用一个队列来保证每一层的节点按顺序加入并弹出队列

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
    ArrayList<Integer> list = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    if(root!=null) queue.add(root);
    while(!queue.isEmpty()){
        TreeNode t = queue.poll();
        if(t.left!=null) queue.add(t.left);
        if(t.right!=null) queue.add(t.right);
        list.add(t.val);
    }
    return list;
}

题目二：把二叉树打印成多行

牛客

描述

给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。

nextLevel 记录下一层的元素个数，toBePrinted 剩余的元素个数，每次从队列弹出一个元素 toBePrinted 减 1 ，toBePrinted 为 0 时开启新的一行。

ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    if(pRoot==null) return ret;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(pRoot);
    int nextLevel=0;
    int toBePrinted=1;
    ArrayList<Integer> list=new ArrayList<>();
    ret.add(list);
    while(!queue.isEmpty()){
        TreeNode t=queue.poll();
        --toBePrinted; 
        if(t.left!=null){
            queue.add(t.left);
            ++nextLevel;
        } 
        if(t.right!=null){
            queue.add(t.right);
            ++nextLevel;
        } 
        list.add(t.val);         
        if(toBePrinted==0 && nextLevel>0){
            list=new ArrayList<>();
            ret.add(list);
            toBePrinted=nextLevel;
            nextLevel=0;
        }

    }
    return ret;
}

题目二：按之字形顺序打印二叉树

牛客

描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

用两个栈交替

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    if(pRoot==null) return ret;
    Deque<TreeNode>[] levels=new Deque[2];
    levels[0]=new LinkedList<>();
    levels[1]=new LinkedList<>();

    levels[0].push(pRoot);
    int current=0;
    int next=1;
    ArrayList<Integer> list = new ArrayList<>();
    ret.add(list);
    while(!levels[0].isEmpty() || !levels[1].isEmpty()){
        TreeNode t = levels[current].pop();
        list.add(t.val);
        if(current==0){
            if(t.left!=null){
                levels[next].push(t.left);

            }
            if(t.right!=null){
                levels[next].push(t.right);
            }
        } else {
            if(t.right!=null){
                levels[next].push(t.right);

            }
            if(t.left!=null){
                levels[next].push(t.left);
            }
        }

        if(levels[current].isEmpty()){
            current = 1 - current;
            next = 1 - next;
            if(!levels[0].isEmpty() || !levels[1].isEmpty()) {
                list = new ArrayList<>();
                ret.add(list);
            }
        }
    }

    return ret;
}