Первый общий предок бинарного дерева

Если у меня есть бинарное дерево поиска, подобное этому, то какой самый низкий общий предок узлов 6 и 1?

Двоичное дерево поиска


algorithm data-structures tree binary-tree binary-search-tree
person Madu    schedule 12.04.2012    source источник
comment
это тестовый пример для проверки правильности работы алгоритма   -  person Madu    schedule 13.04.2012
comment
В данном случае ответом будет 8, но я видел людей, которые также отвечали 6   -  person BrokenGlass    schedule 13.04.2012
comment
люди отвечают 6 в подобном случае или есть какая-то разница в этом случае. Можете ли вы сказать мне точный ответ?   -  person Madu    schedule 13.04.2012

Ответы (1)


arrow_upward
4
arrow_downward

Согласно определению самого младшего общего предка в Википедии, я исправляюсь:

Наименьший общий предок (LCA) — это понятие в теории графов и информатике. Пусть T — корневое дерево с n узлами. Наименьший общий предок определяется между двумя узлами v и w как наименьший узел в T, у которого оба v и w являются потомками (где мы позволяем узлу быть потомком самого себя).

Так что да, исходя из этого определения, правильный ответ будет 6. Если это вопрос интервью, было бы хорошо уточнить заранее с интервьюером.

person BrokenGlass    schedule 13.04.2012