剑指Offer-面试题32-I-从上到下打印二叉树

2020-05-01

题目描述

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
给定二叉树: [3,9,20,null,null,15,7]

1	[3,9,20,15,7]

提示：节点总数 <= 1000

思路

对二叉树进行层序遍历，使用一个队列来存储访问过的节点，根据队列的先进先出特点，先将根节点入队，然后遍历队列，让当前节点出队，访问这个结点的值，然后再将当前节点的左右子节点入队。当队列为空，则遍历结束。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 class Solution{
     public int[] levelOrder(TreeNode root){
         if(root == null){
             return new int[0];
         }
         Queue<TreeNode> queue = new LinkedList<>();
         ArrayList<Integer> list = new ArrayList<>();
         queue.add(root);   //根节点入队
         while(!queue.isEmpty()){   //当队列不为空
             TreeNode node = queue.poll();  //出队
             list.add(node.val);    //访问值
             if(node.left != null){ //左节点不为空，则入队
                 queue.add(node.left);
             }
             if(node.right != null){    //右节点不为空，则入队
                 queue.add(node.right);
             }
         }
         int[] result = new int[list.size()];
         for(int i=0;i<result.length;i++){
             result[i] = list.get(i);
         }
         return result;
     }
 }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。