Recursively and iteratively solution in Python
Basically, this question is recursively. Or we can say, the tree structure is recursively, so the recursively solution maybe easy to write:\n\nTC: O(b) SC: O(lo
Basically, this question is recursively. Or we can say, the tree structure is recursively, so the recursively solution maybe easy to write:\n\nTC: O(b) SC: O(log n)\n\n    class Solution:\n      def isSymmetric(self, root):\n        if root is None:\n          return True\n        else:\n          return self.isMirror(root.left, root.right)\n\n      def isMirror(self, left, right):\n        if left is None and right is None:\n          return True\n        if left is None or right is None:\n          return False\n\n        if left.val == right.val:\n          outPair = self.isMirror(left.left, right.right)\n          inPiar = self.isMirror(left.right, right.left)\n          return outPair and inPiar\n        else:\n          return False\n\nThe essence of recursively is Stack, so we can use our own stack to rewrite it into iteratively:\n\n     class Solution2:\n      def isSymmetric(self, root):\n        if root is None:\n          return True\n\n        stack = [[root.left, root.right]]\n\n        while len(stack) > 0:\n          pair = stack.pop(0)\n          left = pair[0]\n          right = pair[1]\n\n          if left is None and right is None:\n            continue\n          if left is None or right is None:\n            return False\n          if left.val == right.val:\n            stack.insert(0, [left.left, right.right])\n\n            stack.insert(0, [left.right, right.left])\n          else:\n            return False\n        return True
[]