102. 二叉树的层序遍历

题意：

解题思路：

思路：
递归(DFS)：O(n)
1. 递归一层记录一层数据，每层level+1；
BFS：O(n)
1. 先将根节点入队
2. 创建队列用来保存节点数据；
4. 对于当前队列中的所有节点，按顺序依次将儿子加入新队列，并将当前节点的值记录在答案中；
5. 继续下一路队列遍历，直到队列为空

PHP代码实现：

class Solution {
    /**
     * @param TreeNode $root
     * @return Integer[][]
     */
    function levelOrder($root) {
        return $this->bfs($root);
        $res = [];
        $this->dfs($res, $root, 0);
        return $res;
        $res = [];
        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_push($res, $list);
        }
        return $res;
    }
    function bfs($root) {
        $res = [];
        if (!$root) return $res;
        $queue = [];
        array_push($queue, $root);
        $level = 0;
        while (!empty($queue)) {
            foreach ($queue as $r) {
                $res[$level][] = $r->val;
                if ($r->left != null) array_push($queue, $r->left);
                if ($r->right != null) array_push($queue, $r->right);
                array_shift($queue);
            }
            $level++;
        }
        return $res;
    }
    function dfs(&$res, $node, $level) {
        if (!$node) return;
        if (count($res) == $level) $res[$level] = [];
        array_push($res[$level], $node->val);
        $this->dfs($res, $node->left, $level + 1);
        $this->dfs($res, $node->right, $level + 1);
    }
}

GO代码实现：

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

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