Java/Ch 04. Trees and Graphs/Q4_10_Check_Subtree/QuestionB.java

[zhouchanghai]

This solution can be improved from O(n*m) to O(n + m), where n is the size of the big tree t1 and m is size of the small tree t2. We can get the size of every subtree of t1 in O(n) and size of t2 in O(m), and then only compare the subtrees of size m in t1 with t2. There are at most n/m subtrees of size m, and each compare costs O(m), so the total cost is O(n/m * m) + O(n) + O(m) = O(n + m).

    public static boolean containsTree(TreeNode t1, TreeNode t2) {
        if (t2 == null) {
            return true; // The empty tree is a subtree of every tree.
        }
        
        boolean[] result = new boolean[1];
        // Get the size of t2
        int m = treeSizeAndMatch(t2, null, -1, null);
        // Get the size of t1 and do the match for subtrees of size m
        int n = treeSizeAndMatch(t1, t2, m, result);
        return result[0];
    }
    
    private static int treeSizeAndMatch(TreeNode r1, TreeNode r2, int matchSize, boolean[] result) 
    {
        if(r1 == null) return 0;
        int leftSize = treeSizeAndMatch(r1.left, r2, matchSize, result);
        int rightSize = treeSizeAndMatch(r1.right, r2, matchSize, result);
        int size = 1 + leftSize + rightSize;
        if(size == matchSize && !result[0]) {
            result[0] = matchTree(r1,r2);
        }
        return size; 
    }
    
    //The same as Q4_10_Check_Subtree/QuestionB.matchTree
    public static boolean matchTree(TreeNode r1, TreeNode r2) { ... }