Symmetric Tree

判断一个树，是不是自身对称
For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

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

解法一：层次遍历

public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode tmp = queue.poll();
                if (tmp != null) {
                    queue.offer(tmp.left);
                    queue.offer(tmp.right);
                    list.add(tmp.val);
                }else{
                    list.add(null);
                }

            }
            int i = 0, j = list.size() - 1;
            while (i <= j) {
                if (list.get(i++) != list.get(j--)) {
                    return false;
                }
            }
        }
        return true;
    }

解法2： 递归

  //递归
    public boolean isSymmetric2(TreeNode root) {
        return isMirror(root, root);
    }

    public boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
                && isMirror(t1.right, t2.left)
                && isMirror(t1.left, t2.right);
    }

解法3 ： 类似解法2的队列

//类似于sameTree的队列
    public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        q.add(root);
        while (!q.isEmpty()) {
            TreeNode t1 = q.poll();
            TreeNode t2 = q.poll();
            if (t1 == null && t2 == null) continue;
            if (t1 == null || t2 == null) return false;
            if (t1.val != t2.val) return false;
            q.add(t1.left);
            q.add(t2.right);
            q.add(t1.right);
            q.add(t2.left);
        }
        return true;
    }