[第二轮] 3/18-3/24 CareerCup 4.8

You have two very 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.

A tree T2 is a subtree of T1 if there exists a node n in T1 such that the subtree of n is identical to T2. That is, if you cut the tree at node n, the two trees would be identical.

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

Do inorder and preorder traversals of two trees. Then KMP or suffix tree to compare traversals. If the traversals of T2 is the substring of T1, the T2 is the subtree of T1

Method: traverse the larger tree(T1) first, if find the identical node to the root of   smaller tree(T2), then compare the subtree tO the smaller tree recursively...
递归有点小小的感觉了。。。慢慢提高。。
https://github.com/1094401996/Ca ... rdot8/foutdot8.java

https://gist.github.com/ThunderXu/5226374
use recursion, But I'm not sure this method will work fine with very large tree, better take some idea from KMP...

https://gist.github.com/kinofrally/5227660
use recursion,but I dont it will work for large tree either...
之前一直在潜水学习大家的代码，最近发帖的人实在是越来越少，所以就把自己菜鸟级的代码发上来了，大家一起加油！！

struct node
{
   int data;
   struct node * left;
   struct node * right;
}

bool checktree(struct node *r1, struct * node r2)
{
    if(r1 == NULL && r2 == NULL) return true;
    if(r1 == NULL || r2 == NULL) retufn false;

    if(r1->data != r2->data) return false;

    return checktree(r1->left, r2->left) && checktree(r1->right, r2->right);
}

bool isSubTree(struct node * t1, struct node * t2)
{
  if(checktree(t1, t2)) return true;
  
  if(isSubTree(t1->left, t2)) return true;
  if(isSubTree(t1->right, t2)) return true;
  return false;
}

递归..感觉效率不高..
https://gist.github.com/chrislukkk/5233603

https://gist.github.com/5252369.git
Using recursion, same as others.

        // helper method to find the position of the root of the subtree at the main tree;
        public static TreeNode FindSubRoot(TreeNode mainRoot, TreeNode subRoot){
                TreeNode ptr1, ptr2;
               
                ptr1 = mainRoot;
                ptr2 = subRoot;
               
                TreeNode result = new TreeNode();
               
                if(ptr1.data == ptr2.data){
                       
                        // if the conditions are the same that they both are the deepest leaves in the tree;
                        if(ptr1.left == null && ptr2.left == null && ptr1.right == null && ptr2.right == null ||
                                       
                           ptr1.left!= null && ptr2.left != null && ptr1.left.data == ptr2.left.data &&
                           ptr1.right!=null && ptr2.right !=null && ptr1.right.data == ptr2.right.data ||
                                       
                           ptr1.left == null && ptr2.left == null && ptr1.right !=null && ptr2.right != null
                           && ptr1.right.data == ptr2.right.data ||
                                       
                           ptr1.right == null && ptr2.right == null && ptr1.left != null && ptr2.left != null
                           && ptr1.left.data == ptr2.left.data ||
                          
                           ptr1.left != null && ptr2.left != null && ptr1.left.data == ptr2.left.data &&
                           ptr1.right != null && ptr2.right != null && ptr2.right.data == ptr2.right.data){
                                result = ptr1;
                        }
                }
               
                else if(ptr1.data != ptr2.data){
                        if(ptr1.left != null){
                                ptr1 = ptr1.left;
                               
                                result = FindSubRoot(ptr1, ptr2);
                        }
                       
                        else if(ptr1.right != null){
                                ptr1 = ptr1.right;
                               
                                result = FindSubRoot(ptr1, ptr2);
                        }
                }
               
                return result;
        }

        // checking if the subtree is in the main tree;
        public static boolean isSubtree(TreeNode mainRoot, TreeNode subRoot) {
                TreeNode ptr1, ptr2, node;
               
                ptr1 = mainRoot;
                ptr2 = subRoot;
               
                // find the position of root of subtree at the main tree;
                ptr1 = FindSubRoot(ptr1, ptr2);
               
                boolean flag = true;

                if(ptr1.data != ptr2.data){
                        flag = false;
                }
               
                else if(ptr1 != null && ptr2 == null || ptr2 != null && ptr1 == null){
                        flag = false;
                }
                       
                if(ptr1.data == ptr2.data && ptr1.left != null && ptr2.left != null){
                        flag = isSubtree(ptr1.left, ptr2.left);
                }
               
                if(ptr1.data == ptr2.data && ptr1.right != null && ptr2.right !=null){
                        flag = isSubtree(ptr1.right, ptr2.right);
                }
                return flag;
        }




/************* Main Method *************/
public static void main(String[] args) {
                System.out.println("\n********* HW 4.7 **************");
                System.out.println("Find if the subtree is part of the main tree");

                TreeNode node16 = new TreeNode();
                TreeNode node17 = new TreeNode();
                TreeNode node18 = new TreeNode();
               
                TreeNode node19 = new TreeNode();
                TreeNode node20 = new TreeNode();
                TreeNode node21 = new TreeNode();
               
                TreeNode node22 = new TreeNode();
                TreeNode node23 = new TreeNode();
                TreeNode node24 = new TreeNode();
               
                node16.setData(15);
                node17.setData(10);
                node18.setData(18);
               
                node19.setData(8);
                node20.setData(12);
                node21.setData(17);
                node22.setData(19);
               
                node23.setData(25);
               
                // subtree node;
                node24.setData(20);
               
                // version 1
//                insertNode(node19, node17);
//                insertNode(node20, node17);
               
                // version 2
//                insertNode(node16, node24);
//                insertNode(node17, node24);
//                insertNode(node18, node24);
//                insertNode(node19, node24);
//                insertNode(node20, node24);
//                insertNode(node21, node24);
//                insertNode(node22, node24);
//                insertNode(node23, node24);
               
                // version 3
                insertNode(node23, node24);
                insertNode(node16, node24);
               
                boolean isSubTree = isSubtree(root, node24);

                System.out.println("Is the subtree in the main tree? \n" + isSubTree);
                /**********************************/




}