首页 > itarticle > leetcode note: 101 symmetric tree

leetcode note: 101 symmetric tree

admin 11月 13, 2020 0

Two methods useful for tree problems.

Problem Description

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

Codes

Method 1: Recursive

def (self, root):
	def isMirror(left, right):
		if(not left and not right):
			return True
		if(not left or not right):
			return False
		return (left.val==right.val) and 
			isMirror(left.left, right.right) and isMirror(left.right, right.left)
	return isMirror(root, root)

This method use a helper function isMirror which receive two nodes and check if they are symmetric. Then by recursive along all the path of the tree to determine if the tree is symmetric.

Method 2: Iterative

def (self, root):
    import Queue
    q=Queue.Queue()
    q.put(root)
    q.put(root)
    while(not q.empty()):
    	left=q.get()
    	right=q.get()
    	if(not left and not right):
    		continue
    	if(not left or not right):
    		return False
    	if(left.val!=right.val):
    		return False
    	q.put(left.right)
    	q.put(right.left)	
    	q.put(left.left)
    	q.put(right.right)
return True

This method uses a queue to push in pairs of nodes that should have the same value.