剑指offer系列之二十一：从上到下打印二叉树

题目描述

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

此题实际上就是二叉树层序遍历方法的考察，具体思路是：使用一个集合（或者栈，但是相对来说使用栈操作会方便一些）来保存遍历的节点，还需要创建一个集合用来保存最后输出的遍历序列。从根节点开始遍历，首先把该节点放入集合中，并输出其值，之后便从集合中移除该节点，不过在此之前需要判断该节点是否有左右孩子，如果有左右（满足其一就可以）孩子，便把左右孩子放入集合中。每次输出值后便把节点具体的值放入遍历集合中，作为最后的返回结果。

下面是基于这种思路写出的代码：

package com.rhwayfun.offer;

import java.util.ArrayList;

public class PrintBiTreeFromTopToBottom {

    static class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;

        }

    }

    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<TreeNode> treeList = new ArrayList<TreeNode>();
        ArrayList<Integer> treeData = new ArrayList<Integer>();
        if(root == null) return treeData;
        int index = 1;
        treeList.add(root);
        while(treeList.size() > 0){
            TreeNode front = treeList.remove(0);
            index--;
            //System.out.print(front.val + " ");
            treeData.add(front.val);
            //如果节点有左右孩子，则将器左右孩子节点放入队列的末尾
            if(front.left != null){
                treeList.add(index++,front.left);
            }
            if(front.right != null){
                treeList.add(index++,front.right);
            }
        }
        return treeData;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        TreeNode node1 = new TreeNode(6);
        TreeNode node2 = new TreeNode(10);
        TreeNode node3 = new TreeNode(5);
        TreeNode node4 = new TreeNode(7);
        TreeNode node5 = new TreeNode(9);
        TreeNode node6 = new TreeNode(11);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;

        ArrayList<Integer> list = new PrintBiTreeFromTopToBottom().PrintFromTopToBottom(root);
        System.out.println();
        for (Integer integer : list) {
            System.out.print(integer + " ");
        }
    }
}