[劍指offer] 從上往下列印二叉樹

題目描述

從上往下列印出二叉樹的每個節點，同層節點從左至右列印。

解題思路

就是二叉樹的層序周遊。借助一個隊列就可以實作。

使用兩個隊列一個存放節點，一個存放值。先将根節點加入到隊列中，然後周遊隊列中的元素，周遊過程中，通路該元素的左右節點，再将左右子節點加入到隊列中來。

注意

Queue

建立的方式：

Queue<TreeNode> queue = new LinkedList<TreeNode>();

用

add

将元素添加到隊列中，用

remove

來移除并傳回隊首元素。

參考代碼

import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

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

    }

}
*/
public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        if(root == null)
            return res;
        //Queue is abstract; 不能用 new Queue<TreeNode>();
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(queue.size() != 0){
            root = queue.remove();
            res.add(root.val);
            if(root.left != null){
                queue.add(root.left);
            }
            if(root.right != null){
                queue.add(root.right);
            }
        }
        return res;
    }
}