Symmetric Tree

Question: 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:

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

You may view the full question here.

Approach 1: Starting with a typical breadth first search style implementation —

//Approach 1:
//Runtime: 2ms
//Memory usage: 37.7MB
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        
        while(!stack.isEmpty()) {
            List<TreeNode> level = new ArrayList();
            while(!stack.isEmpty()){
                TreeNode currNode = stack.pop();
                if(currNode!=null){
                    level.add(currNode.left);
                    level.add(currNode.right);   
                }                
            }
            int i = 0;
            int[] values = new int[level.size()];
            for(TreeNode node : level){
                stack.push(node);
                if(node!=null){
                    values[i] = node.val;
                } else {
                    values[i] = -1;
                }
                i++;
            }
            if(!compare(values)){
                return false;
            }
        }
        return true;
    }
    
    private boolean compare(int[] values){
        int size = values.length;
        for(int i = 0, j = size-1; i<j; i++, j--){
            if(values[i]!=values[j]){
                return false;
            }
        }
        return true;
    }
}

Find more posts here.

Cheers & Chao!