Amazon OA2 due on 12/15

dengke 发表于 2015-12-13 09:15
http://algorithms.tutorialhorizon.com/given-two-binary-trees-check-if-one-binary-tree-is-a-subtree-o ...

我OA没遇到subtree所以不知道具体要求.
不过tree serialization的时候, 如果tree含重复节点, 是不能用inorder+preorder/postorder做线性化的.如果subtree这道题说可以有duplicate node.那么这两种O(N)做法就不ok,只有用naive的方法了.
当然如果subtree说了不能有duplicate, 就没问题

leonidas1573 发表于 2015-12-13 09:18
我OA没遇到subtree所以不知道具体要求.
不过tree serialization的时候, 如果tree含重复节点, 是不能用in ...

recursion也是O（N）的算法啊，你写成iterator本质上没区别的。

recursion是O(N)么.我看到的算法是

1. 
   
2. class TreeNode {
   
3.         int val;
   
4.         TreeNode left;
   
5.         TreeNode right;
   
6.         TreeNode(int x) { val = x; }
   
7. }
   
8. 
   
9. public class Subtree {
   
10.         public boolean isSubTree(TreeNode T1, TreeNode T2) {
    
11.                 if (T2 == null)        return true;
    
12.                 if (T1 == null)        return false;
    
13.                 return (isSameTree(T1,T2) || isSubTree(T1.left, T2) || isSubTree(T1.right, T2));
    
14.         }
    
15.         public boolean isSameTree(TreeNode T1, TreeNode T2) {
    
16.                 if (T1 == null && T2 == null)        return true;
    
17.                 if (T1 == null || T2 == null)        return false;
    
18.                 if (T1.val != T2.val)        return false;
    
19.                 return (isSameTree(T1.left, T2.left) && isSameTree(T1.right, T2.right));
    
20.         }
    
21. }
    

复制代码

leonidas1573 发表于 2015-12-13 09:31
recursion是O(N)么.我看到的算法是

是O(N)啊。因为每个node都会遍历的。

谢谢楼主分享，很详细呢，祝楼主马上来video, offer!!!

leonidas1573 发表于 2015-12-13 09:31
recursion是O(N)么.我看到的算法是

recursion复杂度是O(m*n), m是T1的nodes数，n是T2的nodes数，这样回答比较准确还是不要说O(N)的号。

leonidas1573 发表于 2015-12-13 09:18
我OA没遇到subtree所以不知道具体要求.
不过tree serialization的时候, 如果tree含重复节点, 是不能用in ...

这题的最优解是迭代遍历存成字符串后，用KMP实现strStr(), 复杂度做到O(n)

leonidas1573 发表于 2015-12-13 09:18
我OA没遇到subtree所以不知道具体要求.
不过tree serialization的时候, 如果tree含重复节点, 是不能用in ...

还有就是你说的这个duplicate的问题只是在constuctr回binary tree是不行的，但是你用inorder + preorder/postorder遍历后再检测substring是没有问题的。

水逼一枚 发表于 2015-12-14 16:09
还有就是你说的这个duplicate的问题只是在constuctr回binary tree是不行的，但是你用inorder + preorder/ ...

1.     b           b
   
2.    /           /
   
3.   a           a
   
4. / \         /
   
5. a   a       a
   
6.            /
   
7.                   a

复制代码

左树右树三种遍历方式全相等.根据13楼code答案是false.

补充内容 (2015-12-15 00:59):
第七行的a向左移动6个字符.图片被弄乱了.

leonidas1573 发表于 2015-12-15 00:58
左树右树三种遍历方式全相等.根据13楼code答案是false.

补充内容 (2015-12-15 00:59):

那就这样，只用preorder先序遍历，对null node添加成'#'拼到字符串里，然后再检测子串，你看看行不行，stack允许null的push.