Detailed explanation of the steps to print a binary tree using Zigzag order in PHP-PHP Tutorial-php.cn

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

php中世界最好的语言

Release： 2023-03-26 22:32:01

Original

1877 people have browsed it

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

Copy after login

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!