**Warm up: Scramble String**

http://buttercola.blogspot.com/2014/09/leetcode-scramble-string.html

http://www.geeksforgeeks.org/tree-isomorphism-problem/

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. Any number of nodes at any level can have their children swapped. Two empty trees are isomorphic.

For example, following two trees are isomorphic with following sub-trees flipped: 2 and 3, NULL and 6, 7 and 8.

We simultaneously traverse both trees. Let the current internal nodes of two trees being traversed be

……

……

**n1**and**n2**respectively. There are following two conditions for subtrees rooted with n1 and n2 to be isomorphic.**1)**Data of n1 and n2 is same.**2)**One of the following two is true for children of n1 and n2……

**a)**Left child of n1 is isomorphic to left child of n2 and right child of n1 is isomorphic to right child of n2.……

**b)**Left child of n1 is isomorphic to right child of n2 and right child of n1 is isomorphic to left child of n2.**Code (Java):**

public class Solution { public boolean isIsoMorphic(TreeNode root1, TreeNode root2) { if (root1 == null && root2 == null) { return true; } if (root1 == null || root2 == null) { return false; } if (root1.val != root2.val) { return false; } return (isIsoMorphic(root1.left, root2.left) && (isIsoMorphic(root1.right, root2.right)) || (isIsoMorphic(root1.left, root2.right) && (isIsoMorphic(root1.right, root2.left))); } public static void main(String[] args) { Solution sol = new Solution(); TreeNode root1 = new TreeNode(1); root1.left = new TreeNode(2); root1.right = new TreeNode(3); root1.left.left = new TreeNode(4); root1.left.right = new TreeNode(5); TreeNode root2 = new TreeNode(1); root2.left = new TreeNode(3); root2.right = new TreeNode(2); root2.right.left = new TreeNode(5); root2.right.right = new TreeNode(4); boolean result = isIsoMorphic(root1, root2); System.out.println(result); } }

## No comments:

## Post a Comment