先解决下楼主的的问题

楼主的第二段代码核心在于数组变量的引用，由于楼主的代码

public function category($fid = 0, $level = 1,$cats = array())
//$cats由于不是引用变量，所以每次递归，$cats都是临时生成的，所以到最后只有几个值。
//而第一段代码中楼主使用的是类变量保存递归结果，$this->cats在整个类中都是有效的。
//楼主改为一下代码即可

public function category($fid = 0, $level = 1,&$cats = array())

输出结果

Array
(
    [0] => Array
        (
            [0] => 顶级分类1
            [1] => 1
        )

    [1] => Array
        (
            [0] => 1-子级1
            [1] => 2
        )

    [2] => Array
        (
            [0] => 4-子级1
            [1] => 3
        )

    [3] => Array
        (
            [0] => 4-子级2
            [1] => 3
        )

    [4] => Array
        (
            [0] => 1-子级2
            [1] => 2
        )

    [5] => Array
        (
            [0] => 顶级分类2
            [1] => 1
        )

    [6] => Array
        (
            [0] => 2-子级1
            [1] => 2
        )

    [7] => Array
        (
            [0] => 2-子级2
            [1] => 2
        )

    [8] => Array
        (
            [0] => 顶级分类3
            [1] => 1
        )

)

我的解决方式

代码

<?php
$pdo = new PDO("mysql:host=localhost;dbname=test", "root", "root");

function getCategories(PDO $pdo, $pid = 0)
{
    $sql = 'SELECT * FROM `category` WHERE pid=:pid';
    $stmt = $pdo->prepare($sql);
    $stmt->bindParam(':pid', $pid, PDO::PARAM_INT);
    $stmt->execute();
    $data = $stmt->fetchAll(PDO::FETCH_ASSOC);
    foreach ($data as &$row) {
        $row['subs'] = getCategories($pdo, $row['id']);
    }
    return $data;
}

$a = getCategories($pdo);
print_r($a);

数据库

输出结果

Array
(
    [0] => Array
        (
            [id] => 1
            [name] => 顶级分类1
            [pid] => 0
            [subs] => Array
                (
                    [0] => Array
                        (
                            [id] => 4
                            [name] => 1-子级1
                            [pid] => 1
                            [subs] => Array
                                (
                                    [0] => Array
                                        (
                                            [id] => 8
                                            [name] => 4-子级1
                                            [pid] => 4
                                            [subs] => Array
                                                (
                                                )

                                        )

                                    [1] => Array
                                        (
                                            [id] => 9
                                            [name] => 4-子级2
                                            [pid] => 4
                                            [subs] => Array
                                                (
                                                )

                                        )

                                )

                        )

                    [1] => Array
                        (
                            [id] => 5
                            [name] => 1-子级2
                            [pid] => 1
                            [subs] => Array
                                (
                                )

                        )

                )

        )

    [1] => Array
        (
            [id] => 2
            [name] => 顶级分类2
            [pid] => 0
            [subs] => Array
                (
                    [0] => Array
                        (
                            [id] => 6
                            [name] => 2-子级1
                            [pid] => 2
                            [subs] => Array
                                (
                                )

                        )

                    [1] => Array
                        (
                            [id] => 7
                            [name] => 2-子级2
                            [pid] => 2
                            [subs] => Array
                                (
                                )

                        )

                )

        )

    [2] => Array
        (
            [id] => 3
            [name] => 顶级分类3
            [pid] => 0
            [subs] => Array
                (
                )

        )

)

array_push() 函数向第一个参数的数组尾部添加一个或多个元素（入栈），然后返回新数组的长度。
该函数等于多次调用 $array[] = $value。

注释：即使数组中有字符串键名，您添加的元素也始终是数字键。（参见例子 2）
注释：如果用 array_push() 来给数组增加一个单元，还不如用 $array[] =，因为这样没有调用函数的额外负担。
注释：如果第一个参数不是数组，array_push() 将发出一条警告。这和 $var[] 的行为不同，后者会新建一个数组。

array_push(array,value1,value2...)