Friday, December 12, 2014

Symmetric Tree

A LeetCode easy level question takes me such long time. -_-|||

The recursive solution is very easy. Keep comparing left.left and right.right  && left.right and right.left.

 public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        return isSymmetricHelper(root.left, root.right);
        
    }
    private boolean isSymmetricHelper(TreeNode left, TreeNode right)
    {
        if (left == null)
            return right == null;
        if (right == null)
            return left == null;
        if (left.val != right.val)
            return false;
        if (!isSymmetricHelper(left.left, right.right))
            return false;
        if (!isSymmetricHelper(right.left, left.right))
            return false;
        return true;
    }

The iterative solution, however is a little bit tricky. The idea is similar to those of tree traversal using iterative method. Here, we use two queues to store nodes from left side of the tree and right side of the tree. Similar to the recursive method, we compare the left.left and right.right && left.right and right.left. Thus, we need to be careful about the order of storing nodes.

public boolean isSymmetric(TreeNode root) {
        if (root == null)
            return true;
        Queue left = new LinkedList();
        Queue right = new LinkedList();
        
        left.add(root.left);
        right.add(root.right);
        while (!left.isEmpty() && !right.isEmpty())
        {
            TreeNode tmp_left = left.poll();
            TreeNode tmp_right = right.poll();
            if ((tmp_left == null && tmp_right != null) || (tmp_left != null && tmp_right == null))
                return false;
            if (tmp_left != null && tmp_right != null)
            {
                if (tmp_left.val != tmp_right.val)
                    return false;
                left.add(tmp_left.left);
                left.add(tmp_left.right);
                right.add(tmp_right.right);
                right.add(tmp_right.left);
                
            }
        }
            return true;
    }

No comments:

Post a Comment