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

发布时间:2024年01月08日

题目

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个位置
  1. 遍历两个结点两个if居然写成了if-else,真蠢啊……
文章来源:https://blog.csdn.net/Miller_6/article/details/135451072
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。