Home >Backend Development >PHP Tutorial >How to implement sequential printing of binary trees in PHP
This article mainly introduces the method of printing binary trees in zigzag order in PHP, and involves the related operation skills of PHP combined with stack traversal of binary trees. Friends who need it can refer to it. I hope it can help everyone.
Question
Please implement a function to print the binary tree in a zigzag pattern, that is, the first line is printed in order from left to right, and the second line is printed in order from left to right. The layers are printed from right to left, the third line is printed from left to right, and so on for the other lines.
Solution idea
Use two stacks
Implementation code
<?php /*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 "</br>"; 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; }
Related recommendations:
PHP implementation of pre-order, in-order and post-order traversal binary tree operation examples
How to use PHP to determine whether a binary tree is symmetrical
JavaScript implements the pre-order, in-order and post-order traversal methods of a binary tree
The above is the detailed content of How to implement sequential printing of binary trees in PHP. For more information, please follow other related articles on the PHP Chinese website!