https://algo.monster/problems/binary_tree_level_order_traversal
a more intuitive python solution for me, would this be ok too?
def level_order_traversal(root: Node) → List[List[int]]:
# WRITE YOUR BRILLIANT CODE HERE
q = deque([(root, 0)])
res = []
while q:
node, level = q.popleft()
if res and level < len(res):
res[level].append(node.val)
else:
res.append([node.val])
if node.left:
q.append((node.left, level + 1))
if node.right:
q.append((node.right, level + 1))
return res
A more intuitive solution to me:
def level_order_traversal(root: Node) → List[List[int]]:
res = []
remaining = [(root, 0)]
while remaining:
e, l = remaining.pop(0)
if l > len(res) - 1:
res.append([e.val])
else:
res[l].append(e.val)
if e.left:
remaining.append((e.left, l+1))
if e.right:
remaining.append((e.right, l+1))
return res
I find this variation a bit more intuitive
def level_order_traversal(root: Node) -> List[List[int]]:
res = []
marker = None
queue = deque([root, marker])
level = []
while len(queue) > 1:
node = queue.popleft()
if node != marker:
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
else:
queue.append(marker)
res.append(level)
level = []
res.append(level)
return res
1 Like
c# implementation using LinkedList as a FIFO Deque
public static List<List<int>> LevelOrderTraversal(Node<int> root)
{
var res = new List<List<int>>();
if (root == null) return res;
var queue = new LinkedList<Node<int>>();
queue.AddFirst(root); // at least one element in the queue to kick start bfs
while (queue.Count > 0)
{ // as long as there is element in the queue
int n = queue.Count;
var newLevel = new List<int>();
// dequeue each node in the current level
for (int i = 0; i < n; i++)
{
var node = queue.Last.Value;
queue.RemoveLast();
newLevel.Add(node.val);
// enqueue non-null children
if (node.left != null) queue.AddFirst(node.left);
if (node.right != null) queue.AddFirst(node.right);
}
res.Add(newLevel);
}
return res;
}
C# Using Queue instead of LinkedList:
public static List<List<int>> LevelOrderTraversal(Node<int> root)
{
var res = new List<List<int>>();
if (root == null) return res;
var queue = new Queue<Node<int>>();
queue.Enqueue(root); // at least one element in the queue to kick start bfs
while (queue.Count > 0)
{ // as long as there is element in the queue
int n = queue.Count;
var newLevel = new List<int>();
// dequeue each node in the current level
for (int i = 0; i < n; i++)
{
var node = queue.Dequeue();
newLevel.Add(node.val);
// enqueue non-null children
if (node.left != null) queue.Enqueue(node.left);
if (node.right != null) queue.Enqueue(node.right);
}
res.Add(newLevel);
}
return res;
}
How about keeping track of level explicitly?
def level_order_traversal(root: Node) -> List[List[int]]:
res = []
root.level = 0
d = deque([root])
while len(d) > 0:
n = d.popleft()
for child in [n.left, n.right]:
if child:
child.level = n.level + 1
d.append(child)
if len(res) < n.level + 1:
res.append([n.val])
else:
res[n.level].append(n.val)
return res
you are welcome
public static List<List<Integer>> levelOrderTraversal(Node<Integer> root) {
// WRITE YOUR BRILLIANT CODE HERE
List<List<Integer>> result = new ArrayList();
Queue<Node<Integer>> q = new LinkedList();
q.add(root);
while(!q.isEmpty())
{
List<Integer> lst = new ArrayList();
int size = q.size();
for(int i = 0; i < size; i++)
{
Node<Integer> n = q.remove();
if(n == null) continue;
lst.add(n.val);
q.add(n.left);
q.add(n.right);
}
if(lst.size() > 0)
{
//System.out.println(lst);
result.add(lst);
}
}
return result;
}
Very good queue’s content analysis resulting in a compact solution.
My solution in js:
function levelOrderTraversal(root) {
const numbers = []
const queue = [[root, 0]]
while(queue.length) {
const [node, lvl] = queue.shift()
if (!numbers[lvl])
numbers[lvl] = [node.val]
else
numbers[lvl].push(node.val)
if (node.left)
queue.push([node.left, lvl + 1])
if (node.right)
queue.push([node.right, lvl + 1])
}
return numbers
}
is the graphic for the explanation missing a slide?
is the graphic for the explanation missing a slide?
IMO, this solution appears to be easier to understand:
def level_order_traversal(root: Node) -> List[List[int]]:
if not root:
return []
res = []
queue = deque([root])
while queue:
level_nodes = []
for _ in range(len(queue)):
node = queue.popleft()
level_nodes.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
res.append(level_nodes)
return res
Another possible approach:
def level_order_traversal(root: Node) -> List[List[int]]:
if not root:
return []
res = []
queue = deque([root])
while queue:
level_nodes = []
for _ in range(len(queue)):
node = queue.popleft()
if node:
level_nodes.append(node.val)
queue.append(node.left)
queue.append(node.right)
if level_nodes:
res.append(level_nodes)
return res
I am amazed by the answer’s approach, which demonstrates a deep understanding of the fact that each while loop indicates a new level.
def level_order_traversal(root: Node) -> List[List[int]]:
q = deque([(root, 0)])
rst = []
while len(q):
node, level = q.popleft()
if not node:
continue
if level >= len(rst):
rst.append([node.val])
else:
rst[level].append(node.val)
q.append((node.left, level + 1))
q.append((node.right, level + 1))
return rst