You have two every large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1.
Example
T2 is a subtree of T1 in the following case:
1 3 / \ / T1 = 2 3 T2 = 4 / 4 T2 isn't a subtree of T1 in the following case:
1 3 / \ \ T1 = 2 3 T2 = 4 / 4public class Solution { /** * @param T1, T2: The roots of binary tree. * @return: True if T2 is a subtree of T1, or false. */ public boolean isSubtree(TreeNode T1, TreeNode T2) { // write your code here if(T2 == null) return true; if(T1 == null) return false; if(T1.val == T2.val){ if(isSameTree(T1,T2)){ return true; } } return isSubtree(T1.left,T2)||isSubtree(T1.right,T2); } public boolean isSameTree(TreeNode t1, TreeNode t2) { if(t1==null && t2==null) { return true; } if(t1==null || t2==null) { return false; } if(t1.val != t2.val) { return false; } return isSameTree(t1.left, t2.left) && isSameTree(t1.right, t2.right); } }