剑指Offer - PHP从上往下打印二叉树
题目描述
从上往下打印出二叉树的每个节点，同层节点从左至右打印。
分析
这里所说的打印其实是二叉树的层级遍历，即从上到下、从左到右遍历每一层级的节点。这种广度遍历使用队列来实现。
- 先将根节点
$root插入队列（节点队列）。 - 然后开始一个 while 循环，循环条件是节点队列不为空。
- 循环弹出节点队列的队头
$head，判断是否有左右节点，有的话插入队尾。 - 由于要返回二叉树的节点的值(val)，所以将
$head->val插入结果数组$res。
代码
<?php
/*class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}*/
function PrintFromTopToBottom($root)
{
if(empty($root)) return []; // 返回的是空数组
$res = array(); // 返回的结果数组
$queueNode = new SplQueue(); // 使用 SplQueue 类
$queueNode->enqueue($root); // 先插入第一个节点
// 循环节点队列，注意 SplQueue 类对象判空要使用 isEmpty()
while(!$queueNode->isEmpty()) {
$head = $queueNode->dequeue(); // 弹出队头
if($head->left != NULL) $queueNode->enqueue($head->left); // 队尾插入
if($head->right != NULL) $queueNode->enqueue($head->right); // 队尾插入
array_push($res,$head->val); // 插入节点值
}
return $res;
}SplQueue 类：通过使用一个双向链表来提供队列的主要功能。
关于 LearnKu
粤公网安备 44030502004330号