【剑指offer】面试题32-从上到下打印二叉树

题目

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

1. 思路

二叉树的广度优先遍历（BFS），借助队列实现，遍历得到的结点元素值存储在列表里。

2.代码（Java实现）

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
   public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
	   ArrayList<Integer> list = new ArrayList<Integer>();
       if (root == null) {
       		// 空二叉树，只输出 [] 
			System.out.println("[]");
    		return list;
    	}
    	Queue<TreeNode> queue = new LinkedList<TreeNode>();
    	queue.add(root);	// 根结点入队
    	while(!queue.isEmpty()) {	// 循环退出条件是队列为空
    		TreeNode p = queue.poll();	// 取出队头结点
    		list.add(p.val);			// 队头结点的值添加进列表
    		if(p.left != null) {		// 取出的队头结点为有左子树
    			queue.add(p.left);		// 其左子树入队
    		}
    		if(p.right != null) {		// 取出的队头结点为有右子树
    			queue.add(p.right);		// 其右子树入队
    		}
       	}
    	System.out.print(list);
    	return list;
    }
}

本文作者： whtli
本文链接： https://hexo.whtli.cn/archives/394445a5.html
版权声明： 遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。