剑指offer-- 32 - I. 从上到下打印二叉树

妖狐艹你老母 2023-02-22 08:20 17阅读 0赞

## 题目描述 ##

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

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

/  
9 20  
/  
15 7

**返回：**

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

**提示：**

节点总数 <= 1000

## 思路：二叉树的层序遍历BFS ##

利用队列层序遍历每个节点  
动态数组ArrayList动态添加每个节点值  
**核心：queue中取出一个节点，再将该节点的左右孩子加入队列**

## 解决方法 ##

/**
     * 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.offer(root);
            //核心：queue中取出一个节点，再将该节点的左右孩子加入队列
            while(queue.size() != 0){
        
                TreeNode node = queue.poll();
                list.add(node.val);
                if(node.left != null)
                    queue.offer(node.left);
                if(node.right != null)
                    queue.offer(node.right);
            }
            //将ArrayList转换为int数组并返回
            int[] res = new int[list.size()];
            for(int i=0; i<res.length; i++)
                res[i] = list.get(i);
    
            return res;
        }
    }