题解 | #从上往下打印二叉树 01#

import java.util.ArrayList;
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<Integer> PrintFromTopToBottom(TreeNode root) {
        
        //辅助
        Queue<TreeNode> q = new ArrayDeque<TreeNode>(); 
        ArrayList<Integer> m = new ArrayList<Integer>();
        //空树
        if(root == null)  
            return m;

        //根节点先进栈
        q.offer(root); 
        while (!q.isEmpty()){ 
            //这一步 栈和队列的区别 后入先出和后入后出
            TreeNode node = q.poll();
            m.add(node.val);
            //左右节点入栈
            if(node.left != null) 
                q.add(node.left);
            if(node.right != null) 
                q.add(node.right);
           
        }
        return m;
    }
}

01：

和栈都是从左到右的遍历，但弹出的顺序不一样

思路：

二叉树的层次遍历就是按照从上到下每行，然后每行中从左到右依次遍历，得到的二叉树的元素值。对于层次遍历，我们通常会使用队列来辅助：

因为队列是一种先进先出的数据结构，我们依照它的性质，如果从左到右访问完一行节点，并在访问的时候依次把它们的子节点加入队列，那么它们的子节点也是从左到右的次序，且排在本行节点的后面，因此队列中出现的顺序正好也是从左到右，正好符合层次遍历的特点。

具体做法：

• step 1：首先判断二叉树是否为空，空树没有遍历结果。
• step 2：建立辅助队列，根节点首先进入队列。不管层次怎么访问，根节点一定是第一个，那它肯定排在队伍的最前面。
• step 3：每次遍历队首节点，如果它们有子节点，依次加入队列排队等待访问。