Блог пользователя Flawless

Lowest Common Ancestor in Binary Tree (Not Binary Search Tree)
Автор Flawless, 12 лет назад, По-английски

What is the most efficient way to find Lowest Common Ancestor in Binary Tree ?

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
12 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

You can use sparse table or RMQ , i think.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i was trying to implement recursively.. but i think using RMQ would be best method

    → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить