题目描述

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

输入描述

二叉树的根节点

输出描述

从上到下，从左到右打印出整棵二叉树

题目分析

节点描述

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

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

    }

}

解法一 　运行时间：28ms　占用内存：636k

import java.util.*;
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

        ArrayList<Integer> list =new ArrayList<Integer>();
        if(root==null) return list;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode t = queue.poll();
            list.add(t.val);
            if(t.left!=null) queue.add(t.left);
            if(t.right!=null) queue.add(t.right);
        }
        return list;
    }
}

　　其实就是一个宽度优先搜索，新建一个list用于顺序存放值，一个queue用来存放节点。每次出队一个节点把节点值存入list中，同时把它的左右子节点依次入队。这样形成一个从上到下从左到右的层次遍历，也就是宽度优先搜索。

解法二 　运行时间：32ms　占用内存：503k

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {

        ArrayList<Integer> listVal =new ArrayList<Integer>();
        if(root==null) return listVal;
        ArrayList<TreeNode> listNode =new ArrayList<TreeNode>();
        listNode.add(root);
        for(int i=0;i<listNode.size();i++){
            TreeNode t = listNode.get(i);
            listVal.add(t.val);
            if(t.left!=null) listNode.add(t.left);
            if(t.right!=null) listNode.add(t.right);
        }
        return listVal;
    }
}

这个和第一种解法的思路是一样的，只是队列换成链表来实现了。