# Is Tree Symmetric

## Problem name: isTreeSymmetric

Problem description is here.

#
# Definition for binary tree:
# class Tree(object):
#   def __init__(self, x):
#     self.value = x
#     self.left = None
#     self.right = None
def isTreeSymmetric(t):
if t is None or (t.left is None and t.right is None):
return True

if t.left is None and t.right is not None:
return False
if t.left is not None and t.right is None:
return False

left_cursor = t.left
right_cursor = t.right
return isEqual(left_cursor, right_cursor)

def isEqual(left, right):
# value
# shape
if left is None or right is None:
return left is None and right is None
return left.value == right.value and isEqual(left.left, right.right) and isEqual(left.right, right.left)


## Time Complexity

O(N) # N is the length of BinaryTree


## Solving Strategy

The symmetric condition means that left subtree of root node is the mirror image of the right subtree of root node.

Then, we can recursively decide this tree is symmetric using two conditions, left node of left subtree is same as right node of right subtree, and right node of left subtree is same as left node of right subtree. If one node is empty, which is None, then the mirror image of the node is also empty. Furthermore, the value of two nodes also need to same.

Since all condition is concatenate using and operator, one condition is false, final result is false, which means that the tree is not symmetric.

태그:

카테고리:

업데이트: