Leetcode–Symmetric Tree

The Problem:

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

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

Notes:

  1. The recursive method is straightforward use DFS, we can raverse the left and right sub tree, and check if return the same result, can use in-order/pre-order/post-order/level-order, here notice that the empty nodes should also be recorded because otherwise sub trees may not have same traversal result but with different structure. See solution I
  2. Another recursive solution is directly compare left.left with right.right, while traversing, see solution II.
  3. The iterative method can be easily achieved use BFS, check for each level if the nodes are symmetric, see solution III.

Java Solution I recursive

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        List<Integer> subL = new ArrayList<Integer>();
        List<Integer> subR = new ArrayList<Integer>();
        subL = traverse(root.left, subL, 0);
        subR = traverse(root.right, subR, 1);
        return(subL.toString().equals(subR.toString()))            
    }
    
    private List<Integer> traverse(TreeNode root, List<Integer> list, int type){
        if(root==null){
            list.add(Integer.MIN_VALUE);
            return list;
        }
        list.add(root.val);
        if(type==0){
            list = traverse(root.left, list, 0);
            list = traverse(root.right, list, 0);
        }
        else{
           list = traverse(root.right, list , 1); 
           list = traverse(root.left, list, 1);
        }
        return list;
    }
}

Java Solution II recursive

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null){
            return true;
        }
        return compare(root.left, root.right, true);
    }
    
    private Boolean compare(TreeNode lt, TreeNode rt, Boolean lastres){
        if(!lastres){
            return false;
        }        
        //one end early
        if((rt == null && lt!=null) || (rt !=null && lt ==null)){
            return false;
        }   
        //if not leaf
        else if(rt !=null && lt != null){
            if(rt.val != lt.val){
                return false;
            }else{
                Boolean outcomp= compare(lt.left, rt.right, true); //match the nodes in mirror
                Boolean incomp = compare(lt.right, rt.left, true);
                return (outcomp&incomp);
            }
        }
        else{//the parent is leaf node
            return true;
        }
    }
}

Java Solution III iterative

It’s wrong but I don’t know why. Any idea?

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        Queue<TreeNode> nxtLv = new LinkedList<TreeNode>();
        int lvCount = 0;
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node.left==null)
                nxtLv.add(new TreeNode(Integer.MAX_VALUE));
            else{
                lvCount++;
                nxtLv.add(node.left);
            }
            if(node.right==null)
                nxtLv.add(new TreeNode(Integer.MAX_VALUE));
            else {
                nxtLv.add(node.right);
                lvCount++;
            }
            //this level finished
            if(q.isEmpty()){
                if(lvCount==0)
                    break;
                lvCount=0;
                if(!checkSymmetric(nxtLv))
                    return false;
                q=nxtLv;
                nxtLv = new LinkedList<TreeNode>();
            }
        }
        return true;   
    }
    
    private boolean checkSymmetric(Queue<TreeNode> q){
        ArrayList<Integer> arr = new ArrayList<Integer>();
        while(!q.isEmpty()){
            TreeNode t = q.poll();
            arr.add(t.val);
        }
        int i = 0;
        int j = arr.size()-1;
        while(i<j){
            if(arr.get(i)!= arr.get(j))
                return false;
            i++;
            j--;
        }
        return true;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s