Java编程题之从上往下打印出二叉树

题目描述

给定一棵二叉树的根节点，从上往下按层打印出这个二叉树，同一层的节点按照从左到右的顺序打印。

例如，给定一个如下所示的二叉树:

    8
   / \
  6   10
 / \  / \
5  7 9   11

打印出的顺序为：8 6 10 5 7 9 11。

解题思路

此题的解法可以用到二叉树的遍历，我们可以用队列来保存每一层的节点。

1. 将根节点加入队列，然后不断遍历队列，如果队列非空，则进行以下操作：
2. 将队列中的节点出队
3. 输出该节点的值
4. 将该节点的左右子节点加入队列
5. 重复步骤一，直到队列为空。

代码实现

import java.util.ArrayList;
import java.util.LinkedList;

public class PrintFromTopToBottom {

    public ArrayList<Integer> printFromTopToBottom(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//将根节点加入队列
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();//将队列中的节点出队
            result.add(node.val);//输出该节点的值
            if (node.left != null) {
                queue.offer(node.left);//将该节点的左子节点加入队列
            }
            if (node.right != null) {
                queue.offer(node.right);//将该节点的右子节点加入队列
            }
        }
        return result;
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }
}

示例说明

示例1

二叉树结构：

    8
   / \
  6   10
 / \
5  7

预期输出结果：

8 6 10 5 7

调用示例：

PrintFromTopToBottom.TreeNode root = new PrintFromTopToBottom.TreeNode(8);
root.left = new PrintFromTopToBottom.TreeNode(6);
root.right = new PrintFromTopToBottom.TreeNode(10);
root.left.left = new PrintFromTopToBottom.TreeNode(5);
root.left.right = new PrintFromTopToBottom.TreeNode(7);
PrintFromTopToBottom solution = new PrintFromTopToBottom();
System.out.println(solution.printFromTopToBottom(root));

示例2

二叉树结构：

    1
     \
      2
       \
        3

预期输出结果：

1 2 3

调用示例：

PrintFromTopToBottom.TreeNode root = new PrintFromTopToBottom.TreeNode(1);
root.right = new PrintFromTopToBottom.TreeNode(2);
root.right.right = new PrintFromTopToBottom.TreeNode(3);
PrintFromTopToBottom solution = new PrintFromTopToBottom();
System.out.println(solution.printFromTopToBottom(root));