Проблемы двоичного дерева.

Проблемы двоичного дерева.

Привет, кто бы ни читал это из будущего, я надеюсь, что ваше путешествие в чудесный мир программной инженерии было потрясающим! Моя началась несколько лет назад, и я должен сказать, что это определенно было одним из лучших событий в моей жизни :-)

Сегодня я пошел на встречу по подготовке к собеседованию слишком рано, в 8:30 утра. Темой были двоичные деревья, и нам было предложено решить несколько задач. (Быстрый привет Джеку Вонгу за организацию встречи!) Что ж, я решил проблемы и подумал, почему бы не написать сообщение в блоге, объясняющее проблемы, а затем решения, которые я придумал.

** Заявление об ограничении ответственности - я не считаю и не утверждаю, что мои решения являются наиболее эффективными. Решения, которые я придумал, - это просто ... решения, которые я придумал o_O

Проблемы:

1. Постройте двоичное дерево (примечание - не двоичное дерево поиска)

2. Найдите все пути к листьям (т. Е. 2–3–9, 2–3–4, 2–8–7, 2–8–1).

3. Найдите самый длинный последовательный путь.

4. Инвертируйте двоичное дерево из предыдущей задачи.

Попробуй! После того, как вы придумали свои собственные решения или, как минимум, обдумали, как бы вы решили эти проблемы, ознакомьтесь с моими решениями.

Решения:

1. Постройте двоичное дерево (примечание - не двоичное дерево поиска)

const Node = function(value) {
  this.value = value;
  this.right = null;
  this.left = null;
};

Node.prototype.insert = function(value) {
  
  let queue = [this],
      node;
  while(queue.length) {
    node = queue.shift();
    if(node.left && node.right)
      queue.push(node.left, node.right);
    else
      break;
  }

  if(!node.left)
    node.left = new Node(value);
  else
    node.right = new Node(value);
};

let root = new Node(2);
[3,8,9,4,7,1].forEach(value => root.insert(value));

Несколько примечаний к приведенному выше коду…

• Я использовал очередь для заполнения дерева, потому что она позволяет мне проходить уровень за уровнем в поисках листьев. Используя эту стратегию, дерево будет заполняться уровень за уровнем слева направо.
• Помещение всех значений в массив и итерация по ним - хороший способ сохранить ваш код чистым.

2. Найдите все пути к листьям (т. Е. 2–3–9, 2–3–4, 2–8–7, 2–8–1).

3. Найдите самый длинный последовательный путь.

Решение - поскольку казалось, что задачи 2 и 3 имеют много общего, я решил использовать одну функцию для решения обеих задач.

const allPaths = function(node) {
  // get all paths to leaves and longest, 
  // increasing by one, sequence

  let maxSequence = 1,
   paths = [];

  const _recurse = function(node, currentSequence, currentPath) {

    if(node.value - currentPath[currentPath.length - 1] === 1)
      currentSequence++;
    else
      currentSequence = 0;

    currentPath.push(node.value);

    if(!node.left && !node.right) {
      // at a leaf, compare currentSequence to maxSequence
      if(currentSequence > maxSequence)
        maxSequence = currentSequence;

      paths.push(currentPath.slice());
      return;
    }

    if(node.left)
      _recurse(node.left, currentSequence, currentPath.slice());

    if(node.right)
     _recurse(node.right, currentSequence, currentPath.slice());
  };

  _recurse(node, 1, []);
  return {paths, maxSequence};
};

Несколько примечаний к приведенному выше коду…

• Я использую метод slice, чтобы у каждого нового кадра стека была собственная копия currentPath. Используя эту стратегию, когда кадр стека извлекается из стека, у кадра под ним будет currentPath, который точно отражает его состояние. Если currentPath был передан без использования метода среза, основной массив будет изменен, и состояние в каждом кадре стека будет изменено.

• {paths, maxSequence} эквивалентно {paths: paths, maxSequence: maxSequence} - сохраняет код чистым.

Если вы находите этот контент чем-то полезным, не стесняйтесь, хлопните мне в ладоши :-) Спасибо!

4. Инвертируйте двоичное дерево из предыдущей задачи.

const invertTree = function(node) {

  const queue = [node];
  let currentNode,
    temp;

  while(queue.length) {
    currentNode = queue.shift();
    if(!currentNode) continue;

    temp = currentNode.left;
    currentNode.left = currentNode.right;
    currentNode.right = temp;

    queue.push(currentNode.left, currentNode.right);
  }
};

Несколько примечаний к приведенному выше коду…

• Опять же, очередь оказывается полезной.
• Чтобы протестировать этот код, я написал стандартный обход по порядку.

const traverse = function(node, arr) { // in order traversal
  if(!node) return;

  traverse(node.left, arr);
  arr.push(node.value);
  traverse(node.right, arr);
};

• Затем использовал следующий код, чтобы убедиться, что инверсия работает ...

let arr = [];
traverse(root, arr);
console.log('Tree before inversion ', arr);

invertTree(root);
arr = [];
traverse(root, arr);
console.log('Tree after inversion ', arr);

И на этом все! Если вы зашли так далеко, я рекомендую вам сосредоточиться ;-)