Начните с создания наборов указателей для каждого вхождения 2 и 3, сохраняя целое число с каждым указателем, показывающим общее расстояние, которое он продвинул до сих пор.Освободите место для примечания на каждом узле дерева, в котором говорится, было ли оно замечено указателем каждого типа, и если да, то расстояние, которое указатель накопил за это время, и источник указателя.
Повторно перемещайте каждый указатель вверх по дереву на один шаг, увеличивая его расстояние.Посмотрите на заметки на узле дерева, которого оно достигло.Если это тот же тип, и расстояние больше, чем расстояние указателя, заменить примечание.Если это тот же тип, и расстояние не больше, два указателя одного типа столкнулись, и вы можете удалить второй указатель.Если это другой тип, у вас есть потенциальный кратчайший путь.
Продолжайте идти, пока каждый указатель не окажется сверху, или каждый указатель не достигнет хотя бы самого короткого найденного пути, потому что после этого любой путьнайдено должно быть длиннее самого короткого найденного пути.
В худшем случае мы работаем до конца и проходим по всему дереву, но только один раз для каждого типа, потому что указатель одного типа, который перемещается доузел, уже пройденный другим указателем того же типа, увидит расстояние до своего узла меньше, чем его собственное расстояние и остановку.Таким образом, в худшем случае стоимость линейна по размеру дерева.