eXeLab
eXeL@B ВИДЕОКУРС !

ВИДЕОКУРС ВЗЛОМ
выпущен 2 июня!


УЗНАТЬ БОЛЬШЕ >>
Домой | Статьи | RAR-cтатьи | FAQ | Форум | Скачать | Видеокурс
Новичку | Ссылки | Программирование | Интервью | Архив | Связь

Русский / Russian English / Английский

Сейчас на форуме: daFix, KDA (+5 невидимых)
 · Начало · Статистика · Регистрация · Поиск · ПРАВИЛА ФОРУМА · Язык · RSS · SVN ·

 eXeL@B —› Программирование —› LCA(Lowest Common Ancestor)
Посл.ответ Сообщение

Ранг: 23.4 (новичок)
Статус: Участник

Создано: 28 сентября 2016 00:29 · Поправил: 28 сентября 2016 00:54 TheNozza New!
Цитата · Личное сообщение · #1

Hello everyone!
Can you say please, do we have a solution to find LCA of two nodes in binary tree visiting every tree node only once?
Nodes only have left, right references without parent.
Requrementes: O(n) time complexity, constant memory space, every tree node is visiting only once.
C, C++, Java, or pseudocode is enough to implement this algo if it exists.
Can anyone show solution of this problem?

Ранг: 407.8 (мудрец)
Статус: Участник

Создано: 28 сентября 2016 04:08 · Поправил: 28 сентября 2016 04:32 dosprog New!
Цитата · Личное сообщение · #2

No. It's too difficult

However go to --> Link <--


Ранг: 508.6 (!)
Статус: Модератор

Создано: 28 сентября 2016 21:39 New!
Цитата · Личное сообщение · #3

TheNozza
are you passing the google & | MS screening?

Ранг: 23.4 (новичок)
Статус: Участник

Создано: 29 сентября 2016 19:12 · Поправил: 29 сентября 2016 19:15 TheNozza New!
Цитата · Личное сообщение · #4

<<are you passing the google & | MS screening?
Not yet. I have found compact solution of this problem. And I want to check if this solution already exists.

In the book "Cracking the Coding Interview, 4 Edition" for task 4.6 there are 3 solutions. You can see there, that algorithm traverses each node of tree more than once.

I can't find in internet how to solve problem visiting every tree node only once.
Here http://blog.gainlo.co/index.php/2016/07/06/lowest-common-ancestor/ you can see mention, that it is possible: "Since we traverse all nodes at most once without external space, both time and space complexity is O(N).", but without code.

Ранг: 566.0 (!)
Статус: Модератор

Создано: 29 сентября 2016 19:28 New!
Цитата · Личное сообщение · #5

note the LCA is a node which has values you looking for in different branches. Use recursion call to find such node.

Ранг: 23.4 (новичок)
Статус: Участник

Создано: 29 сентября 2016 20:46 · Поправил: 29 сентября 2016 20:52 TheNozza New!
Цитата · Личное сообщение · #6

can you show a code? for example post url to code in internet, which solves this problem. My solution has ~ ten strings of code, and of course it uses recursion.

Ранг: 566.0 (!)
Статус: Модератор

Создано: 29 сентября 2016 22:05 New!
Цитата · Личное сообщение · #7

If you have solution what else do you want?
 eXeL@B —› Программирование —› LCA(Lowest Common Ancestor)

Оригинальный DVD-ROM: eXeL@B DVD !

Вы находитесь на форуме сайта EXELAB.RU
Проект ReactOS