CTCI 4.3: Учитывая двоичное дерево, создайте алгоритм, который создает связанный список всех узлов на каждой глубине.

Question

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

Правильно ли это реализация/мыслительный процесс? И на этой ноте, что является эффективным способом для меня проверить мою собственную реализацию, не создавая разные двоичные деревья для ввода?

#Given a binary tree, design an algorithm which creates a linked list of all the nodes at each depth. 
#(e.g if you have a tree with depth D, you'll have D linked lists). 

#Space: O(N) 
#Time: O(N) 
def linked_list_hash(head) 
    level_hash = {} 
    level_hash[1] = LinkedList.new(head) 
    dfs(head, level_hash) 
    level_hash 
end 

def dfs(node, level_hash) 
    new_level = level_hash.keys.last+1 
    level_hash[new_level] = LinkedList.new 
    adj(node).each do |child| 
    level_hash[new_level].insert(child) 
    dfs(child, level_hash) 
    end 
end 

private 
def adj(node) 
    [node.left, node.right] 
end 

Answer 1

Один вопрос: dfs создает новый level_hash[new_level] каждый раз, когда это называется. Но он получает один раз для каждого узла, поэтому вы будете переписывать свои списки каждый раз, когда найдете новый узел. Не уверен, есть ли другие проблемы, но тот выскочил.

Ваш процесс мышления, кажется, в порядке. Я бы подумал о том, чтобы сделать BFS вместо DFS для такой проблемы, поскольку вы пытаетесь группировать вещи по глубине. Однако подход, основанный на DFS, работает.

Чтобы проверить свой код, вы можете начать с его рассуждения и вытащить резину, которая улавливает множество ошибок. В противном случае просто нет замены для тестирования вашего кода с фактическим вводом. Меня попросили сделать это в интервью. При тестировании вы хотите убедиться, что получите хороший обзор своего кода; попробуйте и опустите все пути кода. И попробуйте найти специальные случаи для проверки (в этом случае, что, если вы переходите в пустое дерево? Или у кого корень не имеет детей?)