Symmetric Tree Cont…

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 2: Let’s quickly analyze the performance of our previous approach —

Approach 1

In approach 1, we do a BFS based operation. We first assimilate all the elements for each level and then do a comparison for symmetrical equality. Consider the example indicated in the diagram above. While checking the elements at the third level, we first read all the elements [1, 3, 3, 2]. And then when we start comparing the elements symmetrically, we discover that the 1!=2 and therefore, return a false.

If we can first read only elements 1 and 2, check for their equality and proceed to read the next elements only if needed — we will be able to save a significant amount of processing time. Something like —

Approach 2

The code for this approach looks like —

//Approach 2:
//Runtime: 1ms
//Memory usage: 34.8MB
/**
 * 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) {
        if(root==null){
            return true;
        }
        Queue<TreeNode> leftQ = new LinkedList();
        Queue<TreeNode> rightQ = new LinkedList();
        if(root.left!=null && root.right!=null){
            if(root.left.val==root.right.val){
                leftQ.add(root.left);
                rightQ.add(root.right);    
            } else {
                return false;
            }
        } else {
            if(root.left==null && root.right==null){
                
            }else {
                return false;
            }
        }
        
        while(!leftQ.isEmpty() && !rightQ.isEmpty()){
            TreeNode left = leftQ.remove();
            TreeNode right = rightQ.remove();
            if(left.left!=null && right.right!=null){
                if(left.left.val==right.right.val){
                    leftQ.add(left.left);
                    rightQ.add(right.right);
                } else {
                    return false;
                }
            } else if(left.left==null && right.right==null){
                //Do nothing
            } else {
                return false;
            }
            
            if(left.right!=null && right.left!=null){
                if(left.right.val==right.left.val){
                    leftQ.add(left.right);
                    rightQ.add(right.left);
                } else {
                    return false;
                }
            } else if(left.right==null && right.left==null){
                //Do nothing
            } else {
                return false;
            }
            
        }
        if(leftQ.isEmpty() && rightQ.isEmpty()){
            return true;
        }
        return false;
    }
}

Find more posts here.

Cheers & Chao!