В вопросе мне дано 2 двоичных дерева, и чтобы проверить, является ли одно двоичное дерево поддеревом другого, фрагмент кода в основном выполняет предварительный обход по деревьям беспокойства и генерирует соответствующие строки. Затем он использует indexOf, чтобы проверить, находится ли одна строка дерева в другой, чтобы доказать, что одно дерево является поддеревом другого. Теперь вопросы говорят о том, что, поскольку генерация и сравнение строк обходятся дорого, как бы я изменил его для n-арных деревьев, кроме выполнения сравнения строк.
Я не уверен, как подойти к вопросу, но у меня есть идея, где я мог бы использовать какой-то HashMap для хранения узлов дерева в качестве ключей и его дочерних элементов в качестве значений. Затем, возможно, сравните два значения дерева по аналогичным ключам, чтобы проверить, является ли дерево поддеревом?
Но как это сделать? Я в замешательстве! нужна небольшая помощь.
здесь фрагмент функций:
//make the Node
interface Node {
value: string ;
left?: Node ;
right?: Node ;
}
function checkSubtree(T1: Node , T2: Node ): boolean {
return PreOrderTraversal(T1).indexOf(PreOrderTraversal(T2)) > - 1 ;
}
function stringFromPreOrder(tree: Node ): string {
if (!tree) {
return "" ;
}
return tree.value + PreOrderTraversal(tree.left) + PreOrderTraversal(tree.right);
Итак, в основном, учитывая это, как я могу заставить его работать лучше для nary tree вместо объединения строк и их сравнения? Кроме того, для ни одного дерева я знаю, что дочерние элементы будут в массиве, и я делаю предварительный заказ на него вместо левого и правого. Но как я могу избежать конкатенации строк, поскольку это дорого?
