LeetCode #101 Symmetric Tree

Posted on | Post modified | In , , , , , , ,

Problem

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

Examples

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

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

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

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

Solution1

Method: (naive one)

Time Complexity:

Space Complexity:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 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):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        
        level = [root]
        
        while level:
            level_element = []
            new_level = []
            break_flag = True

            for node in level:
                if node:
                    level_element.append(node.val)
                    break_flag = False
                    new_level.append(node.left)
                    new_level.append(node.right)
                else:
                    level_element.append(None)
            
            if break_flag:
                break
            
            if level_element != level_element[::-1]:
                return False
            
            level = new_level
        
        return True

Solution2

Method: Recursive

Time Complexity: O(n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.helper(root, root)
    
    def helper(self, left, right):
        if not left and not right:
            return True
        elif not left or not right:
            return False
        else:
            return (left.val == right.val) and \
                   self.helper(left.left, right.right) and \
                   self.helper(left.right, right.left)

Solution3

Method: Iterative

Time Complexity: O(n)

Space Complexity: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# 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):
        """
        :type root: TreeNode
        :rtype: bool
        """
        queue = collections.deque([root, root])
        
        while queue:
            left = queue.popleft()
            right = queue.popleft()
            
            if not left and not right:
                continue
            elif not left or not right:
                return False
            else:
                if left.val == right.val:
                    queue.append(left.left)
                    queue.append(right.right)
                    queue.append(left.right)
                    queue.append(right.left)
                else:
                    return False
        
        return True