Home>Article>Backend Development> PHP method to print binary trees in zigzag order

PHP method to print binary trees in zigzag order

jacklove
jacklove Original
2018-05-22 16:53:11 1368browse

This article explains how PHP implements printing of binary trees in zigzag order.

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, the second layer is printed in order from right to left, and the third layer is printed in order from right to left. Lines are printed from left to right, and so on for other lines.

Solution idea

Use two stacks

Implementation code

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

This article explains how PHP implements printing binary trees in zigzag order, more For relevant knowledge, please pay attention to the php Chinese website.

Related recommendations:

php nginx real-time output implementation method

PHP implementation to find the entry node of the ring in the linked list

PHP Class SoapClient not found processing method

The above is the detailed content of PHP method to print binary trees in zigzag order. For more information, please follow other related articles on the PHP Chinese website!

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn