Создано: 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?
Создано: 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.