Home [Algorithm] Level Order Traversal of Binary Tree
Post
Cancel

[Algorithm] Level Order Traversal of Binary Tree

https://www.educative.io/m/level-order-traversal-binary-tree

문제

Given the root of a binary tree, display the node values at each level. Node values for all levels should be displayed on separate lines. Let’s take a look at the below binary tree..

풀이

  • binary tree traversal
  • level order
  • deque

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# Using two queues
def level_order_traversal(root):
  if root == None:
    return

  queues = [deque(), deque()]

  current_queue = queues[0]
  next_queue = queues[1]
  
  current_queue.append(root)
  level_number = 0

  # 🔑
  while current_queue:
    temp = current_queue.popleft()
    print(str(temp.data) , end = " ")

    if temp.left != None:
      next_queue.append(temp.left)

    if temp.right != None:
      next_queue.append(temp.right)

    if not current_queue:
      print()
      level_number += 1
      current_queue = queues[level_number % 2] 
      next_queue = queues[(level_number + 1) % 2]
  print()
  
arr = [100,50,200,25,75,350]
root = create_BST(arr)
print("\nLevel Order Traversal:\n", end = "")
level_order_traversal(root)

https://github.com/restato/Algorithms/blob/master/Array/find_the_missing_number_in_the_array.py

정리

  • Runtime Complexity: Linear, O(n)
  • Memory Complexity: Linear, O(n)
This post is licensed under CC BY 4.0 by the author.

[Algorithm] 1544. Make The String Great

[Algorithm] Merge two sorted linked lists