题解 | #求二叉树的层序遍历#

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型二维数组
 */
function levelOrder( $root )
{
    if($root == null){
        return [];
    }
    $res = []; // 返回结果
    $list = []; // 队列
    $list[] = $root;
    $levelNum = [];
    $levelNum[0] = 1; // 第一层是1个
    $currLevel = 0;
    $currLevelPop = 0;
    while(!empty($list)){
        $pop = array_shift($list);
        $currLevelPop++;
        if($pop->left != null){
            $list[] = $pop->left;
            $levelNum[$currLevel+1]++;
        }
        if($pop->right != null){
            $list[] = $pop->right;
            $levelNum[$currLevel+1]++;
        }
        if(empty($res[$currLevel])){
            $res[$currLevel] = [];
        }
        $res[$currLevel][] = $pop->val;
        if($currLevelPop == $levelNum[$currLevel]){
            // 本层已经pop完了
            $currLevel++;
            $currLevelPop = 0;
        }
    }
    return $res;
}

层序遍历：每一层从左到右的遍历，=BFS广度优先搜索

方法：队列法。每次从队列左边pop一个元素，就把pop的这个元素的子节点从队列右边放入队列。本题的难点在于需要分层输出，如果不需要分层从队列过一遍即可。