Leetcode Symmetric Tree

Tags: , ,

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

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

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

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

 Analysis
This problem can be easily solved using a recursive algorithm.  We defined a method with the following signature:
 
equal(left, right)

then we recursively call equal(left.left, right.right) and equal(left.right, right.left)

The method returns false as long as only one of the two nodes is null, or the two nodes contains different values. 

Java Implementation:

Iterative Algorithm

We can use level order traverse to solve this problem.  We define two queues: curLevel and nextLevel. Initially, the root is inserted into curLevel. Then for each element in curLevel, its children are inserted into the nextLevel with the constraints that the left child comes before the right child. 

Before the next round, we check whether the elements in the nextLevel is symmetric. To make this check faster, we use ArrayList as the queue, because it supports fast index based look up.  

Different from a standard level order traverse, in which a null child is not inserted into the nextLevel queue. However, to solve this problem, we have to insert a null child into the nextLevel queue. Otherwise, both A = [3, null, null, 3], and B = [null, 3, null, 3] will become [3, 3], which is symmetric. However, B is not symmetric. 

So we need to record the null pointer in the nextLevel queue to represent the structure of the tree.

Level order traverse: Java Implementation

An improved solution

The above implementation may not pass certain kinds to test cases, Here is an improved solution. For each level, there are two queues: leftQ and rightQ.

 The leftQ aims to record the left half and the rightQ aims to record the right half of the nodes for the next level, but they are in the contrary direction.

See the following java implementation:

 

Reference:

https://leetcode.com/problems/symmetric-tree/

http://www.geeksforgeeks.org/symmetric-tree-tree-which-is-mirror-image-of-itself/

http://fisherlei.blogspot.com/2013/01/leetcode-symmetric-tree.html

http://www.programcreek.com/2014/03/leetcode-symmetric-tree-java/