Golang solution (9ms)


  • 0

    Iterative BFS Solution

    • Maintain a level node count levelSize to keep track of how many nodes are left to be processed in each level.
    • Append the node values for each level to the levelNodes slice
    • Whenever levelSize becomes 0 it means that we're done processing all the nodes in the current level. This is where we need to append a copy of levelNodes to the two dimensional slice result.
    • Note that we cannot append levelNodes directly to the result slice because for each level they point to the same storage in memory. That is why we allocate a new buffer tmp each time and copy the values from levelNodes.
    func levelOrder(root *TreeNode) [][]int {
        if root == nil { return nil }
        result := [][]int{}
        q, levelNodes := []*TreeNode{}, []int{}
        q = append(q, root)
        levelSize := len(q)
        for len(q) != 0 {
            node := q[0]
            q = q[1:]
            levelSize--
            if node.Left != nil { q = append(q, node.Left) }
            if node.Right != nil { q = append(q, node.Right) }
            levelNodes = append(levelNodes, node.Val)
            if levelSize == 0 {
                tmp := make([]int, len(levelNodes))
                copy(tmp, levelNodes)
                levelNodes = nil
                result = append(result, tmp)
                levelSize = len(q)
            }
        }
        return result
    }
    

    Recursive DFS Solution

    func levelOrder(root *TreeNode) [][]int {
        result := [][]int{}
        levelOrderHelper(root, 0, &result)
        return result
    }
    
    func levelOrderHelper(node *TreeNode, level int, result *[][]int) {
        if node == nil { return }
        if level == len(*result) { *result = append(*result, []int{}) }
        (*result)[level] = append((*result)[level], node.Val)
        levelOrderHelper(node.Left, level + 1, result)
        levelOrderHelper(node.Right, level + 1, result)
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.