剑指Offer - PHP按之字形顺序打印二叉树
题目描述
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
输入:
{8,6,10,5,7,9,11}
输出:
[[8],[10,6],[5,7,9,11]]
分析
这道题与“把二叉树打印成多行”类似，只不过这道题在返回结果数组前，根据层级判断是否需要从右到左顺序输出。
代码
/**
* 节点
*/
class TreeNode{
var $val;
var $left = NULL;
var $right = NULL;
function __construct($val){
$this->val = $val;
}
}
<?php
namespace app\controller;
class Index
{
/**
* 广度优先搜索
*
* @param $pRoot
* @return null
*/
public function BFS($pRoot)
{
if ($pRoot == null) return [];
$queue = new \SplQueue();
$queue->enqueue([$pRoot]); // 初始化：第一层放根节点
$list = []; // 存放结果数组
while (!$queue->isEmpty()) {
$currentRoot = $queue->dequeue(); // 取出队列头节点
list($level, $node) = each($currentRoot); // 键为层级，值为节点
$list[$level][] = $node->val; // 放入结果数组
if ($node->left) $queue->enqueue([$level + 1 => $node->left]); // 左节点放入队列，层级加1
if ($node->right) $queue->enqueue([$level + 1 => $node->right]);// 右节点放入队列，层级加1
}
// 根据层级翻转节点
return array_map(function ($k) {
if ($k % 2 != 0) return array_reverse($k);
}, $list);
}
}
关于 LearnKu
粤公网安备 44030502004330号