【第三轮】7.14-7.20 CareerCup 4.8

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 Tl.
A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2. That is, if you cut off the tree at node n, the two trees would be identical.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
check if b1 has the root of b2, if not, return false; if true, check the value of nodes one by one(here use an arraylist)
【时间复杂度】
O(mn)
【空间复杂度】
O(n)
【gist】
https://github.com/donnice/donnice/blob/master/Q4_8
【Test】
                     5                                                               
                2                  8                              
          1          4       7                                          
                3         6   

好久不来，上次说暂时休息后就一下子拉下来了 >.< 继续
【解题思路】
for all nodes in T1 that the same as the root of T2, check if this is the subtree of T1 that the same as T2
【时间复杂度】
O(n+km)
worst case : O(m*n)
ps: n--Node# in t1
     m--Node# in t2
      k--occurence of t2 root in t1
【空间复杂度】
O(log m + log n)  for recursion calls
【gist link】 https://gist.github.com/JoyceeLee/690e6bba1b4631aa9fff

【解题思路】
Firstly, do pre-order traversal for T1 to find a node equals to the root of T2;
Then check if this subtree of T1 is the same with tree T2;
【时间复杂度】
O(n+km)
where n is the number of nodes in T1, m is the number of nodes in T2, k is the number of nodes in T1 that are equal to the root of T2;
The worst case is O(m*n)
【空间复杂度】
O(log m + log n)  for recursion calls
【gist link】 https://gist.github.com/jyhjuzi/2c5192865cd2fefdaaf6

【解题思路】
Recursion:
Check is subtree from root node.
If not recursively call function on both left subtree and right subtree.

【时间复杂度】
O(N*M) -  N is large tree, M is the one with small amount of nodes

【空间复杂度】
O(Height of N + Height of M)

【gist link】
https://gist.github.com/chrislukkk/905c242ada37ac3caf95
Helper class: https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【解题思路】
traverse T1 by level order
check whether the value of nodes in T1 and T2 equal each other.

【时间复杂度】
O(mn) worst case


【空间复杂度】
O(logm + logn)



【gist link】
https://gist.github.com/happyWinner/00db927f38cd2955e3cf

【解题思路】
一开始被百万的数据量给搞糊涂了，以为一棵树装不到内存里必须要拆分啊有木有
后来无耻的翻了下书，发现其实思路和自己开始想的是一样的，都是先比较root，然后再比较subtree，然后就是写2个简单的第归
另外书上第一种解法好奇葩有木有。。。
【时间复杂度】
O(mn)
【空间复杂度】
O(n)
【gist】
https://gist.github.com/Noahsark/2b021566d3862b4bb20c

【解题思路】Recursion: if the subtree node is in the tree, when find the node then check if it is the subtree; else check the left and right side of the tree.

【时间复杂度】
O(N*M) -  N is large tree, M is the one with small amount of nodes

【空间复杂度】
O(N)

【gist link】https://gist.github.com/bitcpf/b85b3ee344637593a88d

【解题思路】
search for T2's root in T1, call the helper function to determine whether it is a subtree.
【时间复杂度】
O(N+kM)
worst case: O(MN)
【空间复杂度】
O(logM+logN)
【gist link】
https://gist.github.com/1575900cb5e3e74211bc
【test case】
pay attention to empty tree cases

【解题思路】Compare root compare subtree then recursion
【时间复杂度】o(mn)
【空间复杂度】o(n)
【gist link】https://gist.github.com/hilda8519/794e24eb177b5523698e

【解题思路】Compare root compare subtree then recursion
【时间复杂度】o(n+km) k is how many times we check subtree  , n for T2, m for T1
【空间复杂度】o(n)
【gist link】https://gist.github.com/xun-gong/178f0cdc80688dd09b84