Advertisement
kai-rocket

Binary Tree Level Order Traversal

Oct 12th, 2021
854
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.84 KB | None
  1. from collections import deque
  2.  
  3. # Definition for a binary tree node.
  4. # class TreeNode:
  5. #     def __init__(self, val=0, left=None, right=None):
  6. #         self.val = val
  7. #         self.left = left
  8. #         self.right = right
  9. class Solution:
  10.     def levelOrder(self, root: TreeNode) -> List[List[int]]:
  11.         # Handle empty root case
  12.         if not root:
  13.             return []
  14.        
  15.         result = []
  16.        
  17.         # Breadth first search
  18.         q = deque([(root, 0)])
  19.        
  20.         # Keep track of previous node length to track when we reach a new depth
  21.         prevnode_depth = -1
  22.        
  23.         # Store values in current level
  24.         level_values = []
  25.        
  26.         while len(q) > 0:
  27.             currnode_tuple = q.popleft()
  28.             currnode = currnode_tuple[0]
  29.             currnode_depth = currnode_tuple[1]
  30.            
  31.             # If level_values is empty, add currnode
  32.             if len(level_values) == 0:
  33.                 level_values.append(currnode.val)
  34.  
  35.             # Else if the currnode is at same level, add currnode val to level_values
  36.             elif currnode_depth == prevnode_depth:
  37.                 level_values.append(currnode.val)
  38.                
  39.             # Else if currnode is not at the same level
  40.             else:
  41.                 # Add level values to result
  42.                 result.append(level_values)
  43.                 # Reset level values
  44.                 level_values = [currnode.val]
  45.            
  46.             # Append currnode's children to BFS
  47.             if currnode.left:
  48.                 q.append((currnode.left, currnode_depth + 1))
  49.             if currnode.right:
  50.                 q.append((currnode.right, currnode_depth + 1))
  51.        
  52.             prevnode_depth = currnode_depth
  53.        
  54.         # Return result array
  55.         result.append(level_values)
  56.         return result
Advertisement
RAW Paste Data Copied
Advertisement