Сложность пространства для поиска поддерева

Может ли кто-нибудь сказать мне, почему следующий код занимает память: O (logN) + O (logM)? Код должен решить проблему: учитывая большое дерево T1, небольшое дерево T2, проверьте, является ли T2 поддеревом T1. Размер примечания (T1) = N и размер (T2) = M. На самом деле я не видел, чтобы была сделана дополнительная память, за исключением результатов bool поддерева() и matchTree(). Но ИМО эта память должна быть O (1). Пожалуйста, поправьте меня, если я ошибаюсь.

boolean containsTree(TreeNode t1, TreeNode t2) {
 if (t2 == null) return true; // The empty tree is always a subtree
 else return subTree(t1, t2);
}

boolean subTree(TreeNode r1, TreeNode r2) {
 if (r1 == null)
 return false; // big tree empty & subtree still not found.
 if (r1.data == r2.data) {
 if (matchTree(r1,r2)) return true;
 }
 return (subTree(r1.left, r2) || subTree(r1.right, r2));
}

boolean matchTree(TreeNode r1, TreeNode r2) {
 if (r2 == null && r1 == null)
 return true; // nothing left in the subtree
 if (r1 == null || r2 == null)
 return false; // big tree empty & subtree still not found
 if (r1.data != r2.data)
 return false; // data doesnt match
 return (matchTree(r1.left, r2.left) && matchTree(r1.right, r2.right));
}
2 ответа

Функция вызывает себя рекурсивно, поэтому, хотя вы явно не используете память, стек будет стоить O (h1) + O (h2) в стеке вызовов. Если дерево достаточно сбалансировано, это то же самое, что и O (logn) + O (logm).


Рекурсия занимает пространство стека, это то, что вы ищете?

licensed under cc by-sa 3.0 with attribution.