Monday, January 19, 2015

Isomorphic Trees

An easier version of Scramble String. Two trees are called isomorphic if one of them can be obtained from other by a series of flips, i.e., by swapping left and right children of a number of nodes. Two empty trees are isomorphic.

Image source: http://www.geeksforgeeks.org/tree-isomorphism-problem/
The above two trees are isomorphic because : 2 & 3, Null & 6, 7 & 8 are flipped.


public boolean isIsomorphic(TreeNode p, TreeNode q){
    if(p == null)
        return q == null;
    if(q == null)
        return false;
    if(p.val != q.val)
        return false;
    return (isIsomorphic(p.left, q.left) && isIsomorphic(p.right, q.right)) 
    || (isIsomorphic(p.left, q.right) && isIsomorphic(p.right, q.left));
}

No comments:

Post a Comment