Detailed explanation of the steps to print a binary tree using Zigzag order in PHP

This time I will bring you a detailed explanation of the steps for printing binary trees in Z-shaped order in PHP. What are the precautions for using PHP to print binary trees in Z-shaped order? The following is a practical case, let's take a look.

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

I believe you have mastered the method after reading the case in this article. For more exciting information, please pay attention to other related articles on the php Chinese website!

Recommended reading:

Detailed explanation of the steps to implement mongoDB singleton mode operation class in php

Why there is a PHP Class SoapClient not found problem and its solution method

The above is the detailed content of Detailed explanation of the steps to print a binary tree using Zigzag order in PHP. For more information, please follow other related articles on the PHP Chinese website!