Leetcode基础刷题PHP解析(103. Binary Tree Zigzag Level Order Traversal)

2019-6-19 星期三 开始吧

上一题链接Leetcode基础刷题之PHP解析(20. Valid Parentheses)

题目描述

这道题的第一版是二叉数的层次遍历(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;
    }
}

另外我发现leetcode只要你不是指数级的运行时间，这里的success结果你千万不要相信，有毒，想了解自己写的代码效率，还是用大O分析。

Github整理地址:https://github.com/wuqinqiang/leetcode-php