Easy recursive Java O(n+m) solution beats 99,9% without KMP (using Hash)


  • 0
    A

    First hash for t is calculated, then it is passed to hashAndCompare which is calculating the hash of s but on each subtree checks whether the current subtree hash is equal to t's hash. Only if we have a hash collision we fully compare both subtrees.

        boolean hasSub = false;
        public boolean isSubtree(TreeNode s, TreeNode t) {
            if (s == null) return t == null;
            hashAndCompare(s, t, hashAndCompare(t, null, 0));
            return hasSub;
        }
        
        private int hashAndCompare(TreeNode s, TreeNode t, int tHash) {
            if (s == null) return 0;
            int myHash = hashAndCompare(s.left, t, tHash) + hashAndCompare(s.right, t, tHash) + (s.val == 0? 1337 : s.val) * 401;
            if (myHash == tHash && !hasSub) hasSub = equals(s, t);
            return myHash;
        }
        
        private boolean equals(TreeNode s, TreeNode t) {
            if (s == null || t == null) return s == t;
            if (s.val != t.val) return false;
            return equals(s.left, t.left) && equals(s.right, t.right);
        }
    

    Details about hash function:
    Hash collisions should occur only once or at most some constant amount of times, depending on the hash function you choose (Integer's hashCode() is very bad here since it's just the number). I just used a random prime and redirected zero to a random number, since we need 0 hash for null nodes. Would work without this, but leafs with 0 value would create much more collisions :). It works well, but you could construct a bad testcase for it. A more sophisticated hashCode would prevent this (especially breaking natural order would probably be beneficial for edge cases).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.