这篇文章主要介绍了PHP实现按之字形顺序打印二叉树的方法,涉及php结合栈遍历二叉树的相关操作技巧,需要的朋友可以参考下。

本文实例讲述了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. { 
12.   if($pRoot == NULL) 
13.     return []; 
14.   $current = 0; 
15.   $next  = 1; 
16.   $stack[0] = array(); 
17.   $stack[1] = array(); 
18.   $resultQueue = array(); 
19.   array_push($stack[0], $pRoot); 
20.   $i = 0; 
21.   $result = array(); 
22.   $result[0]= array(); 
23.   while(!emptyempty($stack[0]) || !emptyempty($stack[1])){ 
24.     $node = array_pop($stack[$current]); 
25.     array_push($result[$i], $node->val); 
26.     //var_dump($resultQueue);echo "</br>"; 
27.     if($current == 0){ 
28.       if($node->left != NULL) 
29.         array_push($stack[$next], $node->left); 
30.       if($node->right != NULL) 
31.         array_push($stack[$next], $node->right); 
32.     }else{ 
33.       if($node->right != NULL) 
34.         array_push($stack[$next], $node->right); 
35.       if($node->left != NULL) 
36.         array_push($stack[$next], $node->left); 
37.     } 
38.     if(emptyempty($stack[$current])){ 
39.       $current = 1-$current; 
40.       $next  = 1-$next; 
41.       if(!emptyempty($stack[0]) || !emptyempty($stack[1])){ 
42.         $i++; 
43.         $result[$i] = array(); 
44.       } 
45.     } 
46.   } 
47.   return $result; 
48. }

Tags: PHP字形顺序 PHP二叉树

分享到：