Skip to content

102. Binary Tree Level Order Traversal

Description

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • -1000 <= Node.val <= 1000.

Solutions

I Queue

Use a queue to traverse the tree level by level.

Complexity:

  • Time complexity: \(O(n)\), where \(n\) is the number of nodes in the tree.
  • Space complexity: \(O(n)\), where \(n\) is the number of nodes in the tree.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
    values, q := make([][]int, 0), [][]*TreeNode{{root}}
    if root == nil {
        return values
    }

    for len(q) > 0 {
        nodes := q[0]
        q = q[1:]

        var levelValues []int
        nextLevelNodes := make([]*TreeNode, 0)
        for _, node := range nodes {
            levelValues = append(levelValues, node.Val)
            if node.Left != nil {
                nextLevelNodes = append(nextLevelNodes, node.Left)
            }
            if node.Right != nil {
                nextLevelNodes = append(nextLevelNodes, node.Right)
            }
        }
        if len(nextLevelNodes) > 0 {
            q = append(q, nextLevelNodes)
        }
        values = append(values, levelValues)
    }
    return values
}