Symmetric Tree

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

For example, this binary tree is symmetric:

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

But the following is not:

    1
   / \
  2   2
   \   \
   3    3

解题思路
（1）
本题想到的解题思路是树的层序遍历，然后比较同一层上的元素是否是对称的。

（2）
在本题梳理思路时，一定要注意同一层上的元素个数不要想当然的认为是2的指数倍，而是上一层中非空元素个数的两倍。做题时在这一点上浪费了好多时间。。

相关知识
（1）Java中的队列
在java5中新增加了java.util.Queue接口，用以支持队列的常见操作。该接口扩展了java.util.Collection接口。

Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用
element()或者peek()方法。

值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

（2）lable的用法
在程序需要跳出时，注意使用lable方式跳出。

（2）Java中的指数函数
Math.pow(double m, double n) 是求m的n次方

自己的代码

package leetcode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

public class SymmetricTree {
	public boolean isSymmetric(TreeNode root) {
		//如果为空树
		if(root == null) return true;
		
		Vector<Integer> v = new Vector<Integer>();
		v.add(root.val);
		Queue<TreeNode> queue = new LinkedList<TreeNode>();
		queue.offer(root);
		while(!queue.isEmpty()){
			TreeNode headNode = queue.poll();
			
			if(headNode.left != null){
				queue.offer(headNode.left);
				v.add(headNode.left.val);
			}
			else 
				v.add(-1);
			if(headNode.right != null){
				queue.offer(headNode.right);
				v.add(headNode.right.val);
			}
			else 
				v.add(-1);
		}
		//System.out.println(v.toString());
		//当树只有一个元素时
		if(v.size() == 1)return true;
		
		boolean isTrue = true;
		int sum = 1;
		int below0 = 1;
		outer:
		while(below0 != 0){
			int size = 2*below0;
			below0 = 0;
			for(int i = 0; i < size/2; i++){
				if(v.get(sum+i) != -1) below0++;
				if(v.get(sum+i) != v.get(sum+size-1-i)){
					isTrue = false;
					break outer;
				}
			}
			below0 *= 2;
			sum += size;
		}
        return isTrue;
    }
	
	public static void main(String[] args) {
		TreeNode node1 = new TreeNode(1);
		TreeNode node2 = new TreeNode(2);
		TreeNode node3 = new TreeNode(2);
		TreeNode node4 = new TreeNode(3);
		TreeNode node5 = new TreeNode(4);
		TreeNode node6 = new TreeNode(4);
		TreeNode node7 = new TreeNode(3);
		TreeNode node8 = new TreeNode(5);
		TreeNode node9 = new TreeNode(5);
		TreeNode node10 = new TreeNode(6);
		TreeNode node11 = new TreeNode(6);
		
		/*node1.left = node2;
		node1.right = node3;
		node2.left = node4;
		node2.right = node5;
		node3.left = node6;
		node3.right = node7;*/
		
		/*node1.left = node2;
		node1.right = node3;
		node2.right = node4;
		node3.right = node7;*/
		
		/*node1.left = node2;
		node1.right = node4;
		node4.left = node5;
		node5.right = node8;*/
		
		node4.left = node5;
		node4.right = node6;
		node5.left = node8;
		node6.right = node9;
		node8.left = node10;
		node9.right = node11;
		
		SymmetricTree st = new SymmetricTree();
		System.out.println(st.isSymmetric(node4));
	}
}