服务器之家

服务器之家 > 正文

PHP实现按之字形顺序打印二叉树的方法

时间:2019-10-25 12:46     来源/作者:重口味AC

本文实例讲述了PHP实现按之字形顺序打印二叉树的方法。分享给大家供大家参考,具体如下:

问题

请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。

解决思路

使用两个栈

实现代码

  1. <?php 
  2. /*class TreeNode{ 
  3.   var $val; 
  4.   var $left = NULL; 
  5.   var $right = NULL; 
  6.   function __construct($val){ 
  7.     $this->val = $val; 
  8.   } 
  9. }*/ 
  10. function MyPrint($pRoot) 
  11.   if($pRoot == NULL) 
  12.     return []; 
  13.   $current = 0; 
  14.   $next  = 1; 
  15.   $stack[0] = array(); 
  16.   $stack[1] = array(); 
  17.   $resultQueue = array(); 
  18.   array_push($stack[0], $pRoot); 
  19.   $i = 0; 
  20.   $result = array(); 
  21.   $result[0]= array(); 
  22.   while(!empty($stack[0]) || !empty($stack[1])){ 
  23.     $node = array_pop($stack[$current]); 
  24.     array_push($result[$i], $node->val); 
  25.     //var_dump($resultQueue);echo "</br>"; 
  26.     if($current == 0){ 
  27.       if($node->left != NULL) 
  28.         array_push($stack[$next], $node->left); 
  29.       if($node->right != NULL) 
  30.         array_push($stack[$next], $node->right); 
  31.     }else
  32.       if($node->right != NULL) 
  33.         array_push($stack[$next], $node->right); 
  34.       if($node->left != NULL) 
  35.         array_push($stack[$next], $node->left); 
  36.     } 
  37.     if(empty($stack[$current])){ 
  38.       $current = 1-$current; 
  39.       $next  = 1-$next; 
  40.       if(!empty($stack[0]) || !empty($stack[1])){ 
  41.         $i++; 
  42.         $result[$i] = array(); 
  43.       } 
  44.     } 
  45.   } 
  46.   return $result; 

希望本文所述对大家PHP程序设计有所帮助。

标签:

相关文章

热门资讯

玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分
玄元剑仙肉身有什么用 玄元剑仙肉身境界等级划分 2019-06-21
男生常说24816是什么意思?女生说13579是什么意思?
男生常说24816是什么意思?女生说13579是什么意思? 2019-09-17
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情
华为nova5pro和p30pro哪个好 华为nova5pro和华为p30pro对比详情 2019-06-22
超A是什么意思 你好a表达的是什么
超A是什么意思 你好a表达的是什么 2019-06-06
抖音撒撒累累是什么歌 撒撒累累张艺兴歌曲名字
抖音撒撒累累是什么歌 撒撒累累张艺兴歌曲名字 2019-06-05
返回顶部