Méthode PHP pour imprimer des arbres binaires en zigzag

Cet article explique comment imprimer des arbres binaires en ordre zigzag en PHP.

Question

Veuillez implémenter une fonction pour imprimer l'arbre binaire en zigzag, c'est-à-dire que la première ligne est imprimée dans l'ordre de gauche à droite, la deuxième couche est imprimée dans l'ordre de de droite à gauche, et le troisième calque est imprimé de droite à gauche. Les lignes sont imprimées de gauche à droite, et ainsi de suite pour les autres lignes.

Idée de solution

Utiliser deux piles

Code d'implémentation

/*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;
 
}

Cet article explique comment PHP imprime les arbres binaires dans l'ordre en zigzag Pour plus de connaissances connexes. , veuillez faire attention au site Web chinois php.

Recommandations associées :

Méthode d'implémentation de sortie en temps réel PHP nginx

Implémentation PHP pour trouver le nœud d'entrée du sonner dans la liste chaînée

PHP Class SoapClient méthode de traitement introuvable

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!