当前位置:   article > 正文

41、PHP 实现按之字形顺序打印二叉树

41、PHP 实现按之字形顺序打印二叉树

题目:PHP 实现 按之字形顺序打印二叉树

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

<?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;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/919780
推荐阅读
相关标签
  

闽ICP备14008679号