Lowest Common Ancestor (LCA)

1.定義

• BST上兩點的共同祖先當中, 離根最遠, 深度最深的那一個共同祖先, 稱作最低共同祖先, 常簡稱為 LCA

2.算法

• 以求取3,5的LCA為例,

  • 1.當root 6比3, 5都大時, 表示3, 5在root的左邊, 將root向左移動到2

  • 2.當root 2比3, 5都小時, 表示3, 5在root的右邊, 將root向右移動到4

  • 3.當root 4介於3,5之間時, root 4即為LCA