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


2019-6-19 期三 


Leetcode基础刷题之PHP解析(20. Valid Parentheses)

80b7076b73c8fd69ea82b275b9c748c2.png

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

0080447d8195ac30b7e8adb0e5d5e748.png

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


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D90 217. Contains Duplicate

>> 下一篇: DOXCX多合一Sass平台有内部邀请码可以免费下载