Leetcode 101. Symmetric Tree (Python)

Related Topic

Depth-First-Search. Tree. Inorder-Traversal.

Description

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

Sample I/O

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

Example 1

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

Example 1

    1
   / \
  2   2
   \   \
   3    3

Note

Bonus points if you could solve it both recursively and iteratively.

Methodology

This question can be solved by Depth First Search.

To check if the tree is symmetric, we need to know if the left subtree is symmetric to the right subtree. We can use normal Inorder traversal for the left subtree to get the left subtree node list and then use special Inorder traversal (traversal the right node first then left node) to get right subtree node list.If the two results lists are same, then the subtree is symmetric. Note that if there is no node or there is one node, the tree is symmetric.

Code

def isSymmetric(self, root: TreeNode) -> bool:
        if root is None: return True
        def dfs_left(root, res):
            if root is None:
                res.append(None)
                return
            res.append(root.val)
            dfs_left(root.left, res)
            dfs_left(root.right, res)
            return res
        def dfs_right(root, res):
            if root is None: 
                res.append(None)
                return
            res.append(root.val)
            dfs_right(root.right, res)
            dfs_right(root.left, res)
            return res
        return dfs_left(root.left, [])==dfs_right(root.right, []) 

BigO

we use in order for both left subtree and right subtree, the total time complexity is O(n)