Symmetric Tree Solutions in Python

# Source : https://leetcode.com/problems/symmetric-tree/
# Author : penpenps
# Time   : 2019-07-09

# Revert right node firstly, then compare with left node
# Time Complexity: O(n)
# Space Complexity: O(n)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # Revert TreeNode
        def revert(node):
            if not node: return
            node.left, node.right = node.right, node.left
            revert(node.left)
            revert(node.right)
        
        def isEqual(left, right):
            if not left and not right: return True
            if not left or not right: return False
            if left.val != right.val:
                return False
            return isEqual(left.left, right.left) and isEqual(left.right, right.right)
        
        if not root:
            return True
        revert(root.right)
        return isEqual(root.left, root.right)

# Source : https://leetcode.com/problems/symmetric-tree/
# Author : penpenps
# Time   : 2019-07-09

# Recursively check whether the child node is symmetric or not
# Time Complexity: O(n)
# Space Complexity: O(n)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # Check whether left and right child are symmetic
        def symmetricEqual(left, right):
            # left and right child are both None, return True
            if not left and not right: return True
            # one of left and right is None, return False
            if not left or not right: return False
            # the value of left and right are not equal, return False
            if left.val != right.val:
                return False
            return symmetricEqual(left.left, right.right) and symmetricEqual(left.right, right.left)
        
        if not root:
            return True

        return symmetricEqual(root.left, root.right)

# Source : https://leetcode.com/problems/symmetric-tree/
# Author : penpenps
# Time   : 2019-07-09

# Level traversal using two queues to keep left and right sub-tree
# Time Complexity: O(n)
# Space Complexity: O(n)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        q1, q2 = [root], [root]
        while q1 and q2:
            n1, n2 = q1.pop(), q2.pop()
            if not n1 and not n2:
                continue
            if not n1 or not n2:
                return False
            if n1.val != n2.val:
                return False
            q1.append(n1.left)
            q1.append(n1.right)
            q2.append(n2.right)
            q2.append(n2.left)
        return not q1 and not q2

# Source : https://leetcode.com/problems/symmetric-tree/
# Author : penpenps
# Time   : 2019-07-09

# Use single queue to store left and right subtree elements in different directions
# Time Complexity: O(n)
# Space Complexity: O(n)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        q = [root, root]
        while q:
            n1, n2 = q.pop(), q.pop()
            if not n1 and not n2:
                continue
            if not n1 or not n2:
                return False
            if n1.val != n2.val:
                return False
            q.append(n1.left)
            q.append(n2.right)
            q.append(n1.right)
            q.append(n2.left)
        return True