欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

PHP实现按之字形顺序打印二叉树的方法

程序员文章站 2022-04-05 08:24:50
问题 请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。 解决思路 使用两个栈...
问题

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

解决思路

使用两个栈

实现代码

/*class TreeNode{

var $val;

var $left = NULL;

var $right = NULL;

function __construct($val){

$this->val = $val;

}

}*/

function MyPrint($pRoot)

{

if($pRoot == NULL)

return [];

$current = 0;

$next = 1;

$stack[0] = array();

$stack[1] = array();

$resultQueue = array();

array_push($stack[0], $pRoot);

$i = 0;

$result = array();

$result[0]= array();

while(!empty($stack[0]) || !empty($stack[1])){

$node = array_pop($stack[$current]);

array_push($result[$i], $node->val);

//var_dump($resultQueue);echo "
";

if($current == 0){

if($node->left != NULL)

array_push($stack[$next], $node->left);

if($node->right != NULL)

array_push($stack[$next], $node->right);

}else{

if($node->right != NULL)

array_push($stack[$next], $node->right);

if($node->left != NULL)

array_push($stack[$next], $node->left);

}

if(empty($stack[$current])){

$current = 1-$current;

$next = 1-$next;

if(!empty($stack[0]) || !empty($stack[1])){

$i++;

$result[$i] = array();

}

}

}

return $result;

}