Leetcode # 101. Symmetric Tree

https://leetcode.com/problems/symmetric-tree/

Solution

Time Complexity: O(len(tree))
Space Complexity: O(len(tree))
(The input and output generally do not count towards the space complexity.)

class Solution:
  def isSymmetric(self, root: Optional[TreeNode]) -> bool:
    cur_level = [[[root.left], [root.right]]] if root else []
    while cur_level:
      cur_ls, cur_rs = cur_level.pop() # cur_rs is reversed
      next_ls, next_rs = [], []
      """
      print(f"{len(cur_ls)}: ", [node.val if node else None for node in cur_ls], 
            f"{len(cur_rs)}: ", [node.val if node else None for node in cur_rs])
      # """
      for i in range(len(cur_ls)):
        cur_l, cur_r = cur_ls[i], cur_rs[i]
        """
        print(cur_l.val if cur_l else "None", 
              cur_r.val if cur_r else "None")
        # """
        if cur_l:
          if not cur_r or cur_l.val != cur_r.val: return False
          next_ls.append(cur_l.left)
          next_ls.append(cur_l.right)
          next_rs.append(cur_r.right)
          next_rs.append(cur_r.left)
        else:
          if cur_r: return False
          next_ls.append(None)
          next_ls.append(None)
          next_rs.append(None)
          next_rs.append(None)
      # if both next_ls and next_rs are [None, None, ..., None]
      if len([node for node in next_ls if node]\
              + [node for node in next_rs if node]) == 0: break
      cur_level.append([next_ls, next_rs])
    return True

Last Updated on 2023/08/16 by A1go