Этот вопрос мне задали в интервью: У меня есть двоичное дерево, и мне нужно найти общего предка (родителя) по двум случайным узлам этого дерева. Мне также дается указатель на корневой узел.
Мой ответ:
Обходите дерево отдельно для обоих узлов, пока не дойдете до ожидаемого узла. Параллельно во время обхода сохранить элемент и следующий адрес в связанном списке. Тогда у нас есть два связанных списка. Поэтому попробуйте сравнить два связанных списка, и последний общий узел в обоих связанных списках является родительским.
Я думаю, что это решение правильное, поправьте меня, если я ошибаюсь. Если это решение правильное, могу ли я узнать, что это единственное лучшее решение для этой задачи или есть другое лучшее решение, чем это!