# Symmetric Tree

Jul 16th, 2021
934
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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