【剑指Offer】022——从上往下打印二叉树 （树）

题目描述

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

解题思路

就是二叉树的层序遍历。借助一个队列就可以实现。
使用两个队列一个存放节点，一个存放值。先将根节点加入到队列中，然后遍历队列中的元素，遍历过程中，访问该元素的左右节点，再将左右子节点加入到队列中来。
注意Queue创建的方式：Queue<TreeNode> queue = new LinkedList<TreeNode>();
用add将元素添加到队列中，用remove来移除并返回队首元素。

参考代码

Java

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

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 需要接口实例化
        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;
    }
}

Python

# -*- coding:utf-8 -*-
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
class Solution:
    # 返回从上到下每个节点值列表，例：[1,2,3]
    def PrintFromTopToBottom(self, root):
        # write code here
        res = []
        if not root:return res
        helper = [root]
        while len(helper) != 0:
            root = helper.pop(0)
            res.append(root.val)
            if root.left:helper.append(root.left)
            if root.right:helper.append(root.right)
        return res

个人订阅号

image