Symmetric Tree

The idea is to write a recursive function isSame() that takes two trees as argument and returns true if trees are mirror and false if trees are not mirror. The isSame() function recursively checks two roots and subtrees under the root. 算法的时间复杂度是树的遍历O(n)，空间复杂度同样与树遍历相同是O(logn)

public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if ( root == null) return true;
        return isEqual(root.left, root.right);
    }
    public boolean isEqual(TreeNode left, TreeNode right){
        if (left == null && right == null ) return true;
        if (left == null ||  right == null ) return false;
        if (left.val !=  right.val ) return false;
        return isEqual(left.left, right.right) && isEqual(left.right, right.left);
    }
}

queue 解法

    public boolean isSymmetric(TreeNode root) {
        if( root == null) return true;

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        TreeNode p = root.left;
        TreeNode q = root.right;
        if(p == null && q == null) return true;
        if(p == null || q == null) return false;
        if(p.val != q.val) return false;
        queue.offer(p);
        queue.offer(q);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size / 2; i++){
                TreeNode cur_p = queue.poll();
                TreeNode cur_q = queue.poll();
                if((cur_p == null && cur_q == null)) continue;
                if( (cur_p == null && cur_q != null) || (cur_p != null && cur_q == null)){
                    return false;
                }

                if(cur_p.val != cur_q.val) return false;

                queue.offer(cur_p.left);  
                queue.offer(cur_q.right);
                queue.offer(cur_p.right);  
                queue.offer(cur_q.left);  

            }

        }

        //if (!queue.isEmpty() ) return false;
        return true;
    }