[Leetcode] 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

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

递归的写法比较好写，每次分别递归比较两个节点的左右和右左以及节点本身的值。使用iterative的方法的话还是需要层次遍历整棵树，由于镜像对称的缘故，每一层除了第一层以外应该都是有偶数个节点的，在判断的时候需要注意，我就在这个地方小跪了。每一层从两头开始进行比较看是否对称。

递归写法

    public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        return isSymmetric(root.left, root.right);
    }
    
    public boolean isSymmetric(TreeNode root1, TreeNode root2) {
        if(root1 == null && root2 == null) return true;
        else if(root1 == null || root2 == null) return false;
        else {
            return (root1.val == root2.val) && isSymmetric(root1.left, root2.right) && isSymmetric(root1.right, root2.left);
        }
    }

iterative的写法

public boolean isSymmetric(TreeNode root) {
        if(root == null) return true;
        ArrayList<TreeNode> array1 = new ArrayList<TreeNode>();
        ArrayList<TreeNode> array2;
        array1.add(root);
        while(array1.size() != 0) {
            array2 = new ArrayList&ltTreeNode>();
            for(TreeNode tr : array1) {
                if(tr.left != null) array2.add(tr.left);
                if(tr.right != null) array2.add(tr.right);
            }
            if(array1.size() == 1 && array1.get(0) == root) { // only the first layer could have only TreeNode
                array1 = array2;
            }
            else {
                if(array1.size() % 2 != 0) return false;
                else {
                    TreeNode first, last;
                    while(array1.size() != 0) {
                        first = array1.get(0);
                        last = array1.get(array1.size() - 1);
                        if(first.val != last.val) return false;
                        if((first.left == null && last.right != null) || (first.left != null && last.right == null)) 
                            return false;
                        if((first.right == null && last.left != null) || (first.right != null && last.left == null))
                            return false;
                        array1.remove(0); array1.remove(array1.size()-1);
                    }
                    array1 = array2;
                }
            }
        }
        
        return true;
    }