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

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

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

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

Создано: 28 сентября 2016 00:29 · Поправил: 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?



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

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

No. It's too difficult

However go to --> Link <--





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

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

TheNozza
are you passing the google & | MS screening?



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

Создано: 29 сентября 2016 19:12 · Поправил: 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.



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

Создано: 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 · Поправил: 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.



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

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

If you have solution what else do you want?


 eXeL@B —› Программирование —› LCA(Lowest Common Ancestor)

Видеокурс ВЗЛОМ