Symmetric Tree

Problem Id: 101 Difficulty: Easy Tag: Tree Tag: Depth-first Search Tag: Breadth-first Search


Intuition

This is similiar to check if 2 trees are the same. The main part of this solution is a preorder traversal of the left sub-tree, while the helping part of it is a mirror preorder traversal of the right sub-tree.

Solution


# 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 root is None:
            return True

        return self.inorder_traversal(root.left, root.right)

    def inorder_traversal(self, l, r):
        if l is None and r is None:
            return True
        elif l is None or r is None:
            return False
        elif r.val != l.val:
            return False
        else:
            return self.inorder_traversal(l.right, r.left) and \
                    self.inorder_traversal(l.left, r.right)