从上往下打印二叉树

1. 题目描述

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

2. 思路

层序遍历使用队列

3. 实现

• java

public class 从上往下打印二叉树
{
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root)
    {
        //检查参数
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null)
        {
            return res;
        }

        //层序遍历使用队列
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //只要队列不为空
        while (!queue.isEmpty())
        {
            //取出队首，放入res
            TreeNode treeNode = queue.removeFirst();
            res.add(treeNode.val);
            //把左节点和右节点加入队列
            if (treeNode.left != null)
            {
                queue.add(treeNode.left);
            }
            if (treeNode.right != null)
            {
                queue.add(treeNode.right);
            }

        }
        return res;
    }
}

• go

//时间复杂度：O(n),二叉树的每个节点遍历一次
//空间复杂度：O(n),二叉树的每个节点入队列一次
func PrintFromTopToBottom(root *TreeNode) []int {
	if root == nil {
		return nil
	}

	res := make([]int, 0)

	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	for len(queue) > 0 {
		removed := queue[0]
		queue = queue[1:]

		res = append(res, removed.Val)
		if removed.Left != nil {
			queue = append(queue, removed.Left)
		}
		if removed.Right != nil {
			queue = append(queue, removed.Right)
		}
	}

	return res
}

4. 参考

• 从上往下打印二叉树_牛客网