【中等】102. 二叉树的层序遍历

题目

102. 二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：
输入：root = [1]
输出：[[1]]

示例 3：
输入：root = []
输出：[]

提示：
树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

解题

func levelOrder(root *TreeNode)(res [][]int) {

    if root==nil{
        return
    }


    nodeArray := []*TreeNode{root}
    left, right :=  0, len(nodeArray)

    for left < right {
        numArray := []int{}
        for ; left < right; left++ {
            numArray = append(numArray, nodeArray[left].Val)
            if nodeArray[left].Left != nil{
                nodeArray = append(nodeArray, nodeArray[left].Left)
            }
            if nodeArray[left].Right != nil{
                nodeArray = append(nodeArray, nodeArray[left].Right)
            }
        }
        res = append(res, numArray)
        nodeArray = nodeArray[right:]
        left, right = 0, len(nodeArray)

    }
    return
}

func levelOrder(root *TreeNode)(res [][]int) {

    if root==nil{
        return
    }

    nodeArray := []*TreeNode{root}

    for len(nodeArray) > 0{
        numArray := []int{}
        nextNodeArray := []*TreeNode{}

        for _, v := range nodeArray {
            numArray = append(numArray, v.Val)
            if v.Left != nil{
                nextNodeArray = append(nextNodeArray, v.Left)
            }
            if v.Right != nil{
                nextNodeArray = append(nextNodeArray, v.Right)
            }
        }
        res = append(res, numArray)
        nodeArray = make([]*TreeNode, len(nextNodeArray)) 
        copy(nodeArray, nextNodeArray)
    }

    return
}

题解

方法一：广度优先遍历法

1

func levelOrder(root *TreeNode) [][]int {
    ret := [][]int{}
    if root == nil {
        return ret
    }
    q := []*TreeNode{root}
    for i := 0; len(q) > 0; i++ {
        ret = append(ret, []int{})
        p := []*TreeNode{}
        for j := 0; j < len(q); j++ {
            node := q[j]
            ret[i] = append(ret[i], node.Val)
            if node.Left != nil {
                p = append(p, node.Left)
            }
            if node.Right != nil {
                p = append(p, node.Right)
            }
        }
        q = p
    }
    return ret
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/241885/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间：O(n)
空间：O(n)

长进

1. 使用内置copy函数拷贝切片时，应注意目标切片必须分配过空间且足够承载复制的元素个数
   所以拷贝前确保分配足够的空间。

slice1 := []int{1, 2, 3, 4, 5}
slice2 := []int{5, 4, 3}
copy(slice2, slice1) // 只会复制slice1的前3个元素到slice2中
copy(slice1, slice2) // 只会复制slice2的3个元素到slice1的前3个位置

2. 遍历两个结点两个if居然写成了if-else，真蠢啊……