Как только вы поместите ваши данные в двоичное дерево поиска, вы можете восстановить их, как показано ниже. Используйте рекурсию, чтобы отслеживать глубину в каждом узле дерева.
При каждом рекурсивном вызове помещайте узел на текущем уровне в хеш-таблицу, используя уровень в качестве ключа и узел в качестве значения.
В JavaScript вы можете использовать массив или литерал объекта для этого. Я храню все в объектном литерале JavaScript, который похож на хеш-таблицу под капотом. Как это:
level = 0
object[level] = [node1] => { '0': [node, node2] }
object[level] = [node2] => { '0': [node1, node2] }
level = 1
object[level] = [node3] => { '0': [node, node2], '1': [node3] }
и т.д ...
Перед нажатием проверьте, существует ли ключ. Если он не существует, просто вставьте узел в ваш хеш, завернутый в массив.
Если ключ существует (имеется в виду коллизия уровня), вызовите разрешение коллизий, просто нажав массив в этой клавише.
Теперь у вас есть все узлы на каждом уровне, которые хранятся в уникальных массивах внутри объекта. Это должно выглядеть так:
{ '0': [ 20 ],
'1': [ 8, 22 ],
'2': [ 4, 12, 24 ],
'3': [ 10, 14 ] } */
Или это, если вы храните весь узел:
{ '0': [ { value: 20, right: [Object], left: [Object] } ],
'1':
[ { value: 8, right: [Object], left: [Object] },
{ value: 22, right: [Object], left: null } ],
'2':
[ { value: 4, right: null, left: null },
{ value: 12, right: [Object], left: [Object] },
{ value: 24, right: null, left: null } ],
'3':
[ { value: 10, right: null, left: null },
{ value: 14, right: null, left: null } ] }
После этого вы можете делать с ними что хотите. Суммируйте значения на каждом уровне, преобразуйте их в связанный список или, в вашем случае, просто проверьте длину массива на нужном уровне. Это даст вам количество узлов.
BinaryTree.prototype.kNodesAtDepth = function(level) {
var levels = {};
var traverse = function(current, depth) {
if (!current) return null;
if (!levels[depth]) levels[depth] = [current.value];
else levels[depth].push(current.value);
traverse(current.left, depth + 1);
traverse(current.right, depth + 1);
};
traverse(this.root, 0);
return levels[level].length;
};
//tests
var bst = new BinaryTree();
bst.add(20, 22, 8, 4, 12, 10, 14, 24);
var nodeCount = bst.kNodesAtDepth(2); //3
console.log(nodeCount); //3