Что не так с моим кодом (реализация BFS на javascript для решения проблемы с leetcode) - PullRequest
Новая
       38

Что не так с моим кодом (реализация BFS на javascript для решения проблемы с leetcode)

0 голосов
/ 23 января 2019

Я реализую BFS-поиск двоичного дерева, чтобы решить проблему с leetCode. Проблема leetCode:

Название: 662. Максимальная ширина двоичного дерева

Описание:

Для заданного бинарного дерева напишите функцию, чтобы получить максимальную ширину данного дерева. Ширина дерева - это максимальная ширина среди всех уровней. Двоичное дерево имеет ту же структуру, что и полное двоичное дерево, но некоторые узлы являются нулевыми.

Ширина одного уровня определяется как длина между конечными узлами (самый левый и самый правый ненулевые узлы на уровне, где нулевые узлы между конечными узлами также учитываются при расчете длины.

Пример:

Ввод: 

       1
     /   \
    3     2
   / \     \  
  5   3     9

Выход: 4 Пояснение: Максимальная ширина, существующая на третьем уровне с длиной 4 (5,3, ноль, 9).

==============

Мой код в Javascript: 

const widthOfBinaryTree = (root) => {
  let nodeItemList = [{ node: root, index: 0 }];
  let ans = 1;
  while (nodeItemList.length > 0) {
    const newNodeItemList = [];
    for (const nodeItem of nodeItemList) {
      if (nodeItem.node.left !== null) {
        newNodeItemList.push({ node: nodeItem.node.left, index: nodeItem.index * 2 });
      }
      if (nodeItem.node.right !== null) {
        newNodeItemList.push({ node: nodeItem.node.right, index: nodeItem.index * 2 + 1 });
      }
    }
    if (newNodeItemList.length === 0) break;
    const begin = newNodeItemList[0].index;
    const end = newNodeItemList[newNodeItemList.length - 1].index;
    ans = Math.max(ans, end - begin + 1);
    nodeItemList = newNodeItemList;
  }
  return ans;
}

Логика мне совершенно подходит после того, как я несколько раз тщательно ее проверил. Но это не удалось при специальном тесте в leetcode.

Вы можете вставить мой код в leetcode, чтобы увидеть тестовый случай неудачи. Проблема ссылка: https://leetcode.com/problems/maximum-width-of-binary-tree/

...