107. 二叉树的层次遍历 II

题意：

解题思路：

思路：
BFS：树中每个节点仅会进队出队一次，所以时间复杂度是 O(n)
1. 先将根节点入队
2. 创建队列用来保存节点数据；
4. 对于当前队列中的所有节点，按顺序依次将儿子加入新队列，并将当前节点的值记录在答案中；
5. 继续下一层队列遍历，直到队列为空

PHP代码实现：

class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrderBottom($root) {
        if (!$root) return [];
        $res = [];
        $queue = [];
        array_push($queue, $root);
        while (!empty($queue)) {
            $list = [];
            foreach ($queue as $r) {
                array_push($list, $r->val);
                if ($r->left != null) array_push($queue, $r->left);
                if ($r->right != null) array_push($queue, $r->right);
                array_shift($queue);
            }
            array_unshift($res, $list);
        }
        return $res;
    } 
    function levelOrderBottom1($root) {
        if (!$root) return [];
        $res = [];
        $queue = [];
        array_push($queue, $root);
        while (!empty($queue)) {
            $len = count($queue);
            $list = [];
            for ($i = 0; $i < $len; $i++) {
                $r = array_shift($queue);
                array_push($list, $r->val);
                if ($r->left != null) array_push($queue, $r->left);
                if ($r->right != null) array_push($queue, $r->right);
            }
            array_push($res, $list);
        }
        krsort($res);
        return $res;
    }
}

GO代码实现：

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func levelOrderBottom(root *TreeNode) [][]int {
    res := make([][]int, 0)
    queue := []*TreeNode{}
    if root == nil {
        return res
    }
    queue = append(queue, root)
    for len(queue) > 0 {
        tmp := []*TreeNode{}
        t := make([]int, 0)
        for i := 0; i < len(queue); i++ {
            t = append(t, queue[i].Val)
            if queue[i].Left != nil {
                tmp = append(tmp, queue[i].Left)
            }
            if queue[i].Right != nil {
                tmp = append(tmp, queue[i].Right)
            }
        }
        queue = tmp
        res = append(res, t)
    }
    lp := 0
    rp := len(res) - 1
    for lp < rp {
        res[lp], res[rp] = res[rp], res[lp]
        lp++
        rp--
    }
    return res
}