103.md

✏️Leetcode基础刷题之(103. Binary Tree Zigzag Level Order Traversal)

2019-06-19 吴亲库里 库里的深夜食堂

---

✏️描述

这道题的第一版是二叉数的层次遍历(Leetcode基础刷题之PHP解析(102. Binary Tree Level Order Traversal)),这一版让我们按照z字形遍历二叉树。什么意思呢，就是说如果当前层是从左往右遍历，那么下一层就从右往左遍历。

✏️题目实例

​

✏️题目分析

解法和层次遍历思路差不多，只是每次用一个标识记录一下当前应该从哪个方向开始遍历，如果是从左往右的话，把当前层的结点值以队列的形式插入到当前集合中，如果是右往左，把当前结点的值依次压入当前栈集合中，然后每层结束，小集合push到大集合中，直到最后。

✏️具体实现

     /**
      * Definition for a binary tree node.
      * class TreeNode {
      *     public $val = null;
      *     public $left = null;
      *     public $right = null;
      *     function __construct($value) { $this->val = $value; }
      * }
      */
     class Solution {
     
         /**
          * @param TreeNode $root
          * @return Integer[][]
          */
         function zigzagLevelOrder($root) {
             if(empty($root)) return [];
             $stack=[];
             $res=[];
             array_push($stack,$root);
              $real=true;  //标识方向
             while(!empty($stack)){
                 $num=count($stack);
                  $level=[];
                 $stack2=[];
                 foreach($stack as $node){
                     if($real) array_push($level,$node->val);
                     else array_splice($level,0,0,$node->val); 
                     if($node->left) array_push($stack2,$node->left);
                     if($node->right) array_push($stack2,$node->right);
                 }
                  $real = !$real;
                 $stack = $stack2;
                 array_push($res,$level);  
             }
             return $res;
         }
     }

---

联系

​