Advertisement
kai-rocket

Symmetric Tree

Jul 16th, 2021
879
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.37 KB | None | 0 0
  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 isLevelSymmetric(self, level_arr: list) -> bool:
  11.         for i in range(math.ceil(len(level_arr) / 2)):
  12.             if level_arr[i] != level_arr[-1-i]:
  13.                 return False
  14.         return True
  15.        
  16.     def isSymmetric(self, root: TreeNode) -> bool:
  17.         # Keep track of current level so I know when to check for symmetry
  18.         curr_level = 0
  19.         # Store level array to check symmetry
  20.         level_arr = []
  21.        
  22.         # BFS
  23.         queue = deque([{
  24.             'node': root,
  25.             'level': 0
  26.         }])
  27.        
  28.         while len(queue) > 0:
  29.             curr_node_dict = queue.popleft()
  30.             # Extract node for convenience
  31.             curr_node = curr_node_dict['node']
  32.             # Extract curr_node_val for the case where curr_node is None
  33.             if curr_node:
  34.                 curr_node_val = curr_node.val
  35.             else:
  36.                 curr_node_val = None
  37.            
  38.             # Once finish a level, check if that level is symmetric
  39.             if curr_node_dict['level'] > curr_level:
  40.                 # If not symmetric, return False
  41.                 if not self.isLevelSymmetric(level_arr):
  42.                     return False
  43.                 # Else continue, reset level_arr, increment curr_level
  44.                 level_arr = [curr_node_val]
  45.                 curr_level += 1
  46.                
  47.             # If still on same level, append curr node's value to level_arr
  48.             else:
  49.                 level_arr.append(curr_node_val)
  50.  
  51.             # If curr_node is None, do not attempt to add children to queue
  52.             if not curr_node:
  53.                 continue
  54.                
  55.             # Add left child to the queue
  56.             queue.append({
  57.                 'node': curr_node.left,
  58.                 'level': curr_node_dict['level'] + 1
  59.             })
  60.  
  61.             # Add right child to the queue
  62.             queue.append({
  63.                 'node': curr_node.right,
  64.                 'level': curr_node_dict['level'] + 1
  65.             })
  66.            
  67.         # If reached end of tree (i.e. finished BFS, i.e. queue is empty), return True
  68.         return True
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement