PHP explains how to print binary trees in zigzag order-PHP Tutorial-php.cn

PHP explains how to print binary trees in zigzag order

jacklove

Release： 2023-04-02 07:42:01

Original

1487 people have browsed it

This article mainly introduces the method of PHP to realize printing binary trees in zigzag order, involving the related operation skills of PHP combined with stack traversal of binary trees. Friends in need can refer to the following

The example of this article describes the implementation of printing binary trees in PHP A method to print a binary tree in zigzag order. Share it with everyone for your reference, the details are as follows:

Question

Please implement a function to print the binary tree in a zigzag format, that is, the first line is as follows Print from left to right, the second layer prints from right to left, the third line prints 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

Articles you may be interested in:

Explanation of how to obtain binary tree image in PHP

Explanation of PHP’s method of obtaining the Kth node from the last in a linked list

#PHP’s method of printing a binary tree from top to bottom explain

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