102 Binary Tree Level Order Traversal ✅¶
Use
List<List<int>>()
to track level values
::: tip Key Points
- queue
- Use Null (a special element) to divide each layer in the queue
- Basic tree BFS
- Note that when inserting null, check where the current queue is empty, otherwise it will loop indefinitely :::
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:
Example 2:
Example 3:
C# Solution¶
using System;
using System.Collections.Generic;
// using System.Linq;
namespace Algorithms.Medium
{
/*
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
*/
public class BinaryTreeLevelOrderTraversal
{
public static List<IList<int>> LevelOrder(TreeNode root)
{
var levels = new List<IList<int>>();
if (root == null) return levels;
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
var levelIndex = 0;
while (queue.Count > 0)
{
levels.Add(new List<int>());
var queueCount = queue.Count;
for (var i = 0; i < queueCount; i++)
{
TreeNode currentNode = queue.Dequeue();
// levels.ElementAt(level).Add(currentNode.val);
levels[levelIndex].Add(currentNode.val);
if (currentNode.left != null) queue.Enqueue(currentNode.left);
if (currentNode.right != null) queue.Enqueue(currentNode.right);
}
levelIndex++;
}
return levels;
}
}
}
C# Tests¶
using System.Collections.Generic;
using Algorithms.Medium;
using Xunit;
namespace AlgorithmTests.Medium
{
public class BinaryTreeLevelOrderTraversalTests
{
[Fact]
public void LevelOrderTest()
{
TreeNode l0 = new TreeNode(3);
l0.left = new TreeNode(9);
l0.right = new TreeNode(20);
l0.right.left = new TreeNode(15);
l0.right.right = new TreeNode(7);
var expectedLevels = new List<List<int>>();
expectedLevels.Add(new List<int> { 3 });
expectedLevels.Add(new List<int> { 9, 20 });
expectedLevels.Add(new List<int> { 15, 7 });
Assert.Equal(expectedLevels, BinaryTreeLevelOrderTraversal.LevelOrder(l0));
}
}
}
Variant: 107. Binary Tree Level Order Traversal II Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]
Other BFS problems