What is the most efficient way to find Lowest Common Ancestor in Binary Tree ?
What is the most efficient way to find Lowest Common Ancestor in Binary Tree ?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | jiangly | 3578 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | tourist | 3565 |
| 8 | maroonrk | 3531 |
| 9 | Radewoosh | 3521 |
| 10 | Um_nik | 3482 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 146 |
| 8 | orz | 146 |
| 10 | pajenegod | 145 |
See at TopCoder Algorithm Tutorials, there is a nice explanation for Lowest Common Ancestor. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
You can use sparse table or RMQ , i think.
i was trying to implement recursively.. but i think using RMQ would be best method
if you don't need online LCA algorithm, I think Tarjan's off-line LCA algorithm would be best one. easy to code an fast enough always :D (maybe fastest)
These are by far the best tutorials I've come across:
1. Finding the lowest common ancestor in rooted trees
2. What are the specifics in implementing an O(N log N) Lowest Common Ancestor algorithm?
Both use the Binary Raising method to calculate LCA. It's the best and most intuitive approach for LCA. Most of the top programmers in my country use this.