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!