Algorithm and data structure
  • Algorithm and data structure
  • Break Away: Programming And Coding Interviews & Cracking coding interview
    • System design and scalability
    • Performance and Complexity
    • Big O Notation
    • Sorting trade-off
    • Selection sort
    • Bubble sort
    • Insertion sort
    • Shell sort
    • Merge sort
    • Quick sort
    • Binary search
    • Recursion
    • Binary tree
    • Breadth First Traversal
    • Depth First Pre-Order
    • Binary search tree
    • Stack
    • Queue
    • Linked list
    • Doubly linked list
    • String
    • Pointer and array
    • Bit manipulation
    • General programming problems
    • Priority queue
    • Balanced binary search tree
    • Binary heap
    • Heap sort
    • Graphs
    • Topological sort
  • Leetcode
    • 1. Two Sum
    • 2. Add Two Numbers
    • 3. Longest Substring Without Repeating Characters
    • 4. Median of Two Sorted Arrays
    • 5. Longest Palindromic Substring
    • 6.ZigZag Conversion
    • 7. Reverse Integer
    • 8. String to Integer (atoi)
    • 9. Palindrome Number
    • 11. Container With Most Water
    • 12. Integer to Roman
    • 13. Roman to Integer
    • 14. Longest Common Prefix
    • 15. 3Sum
    • 16. 3Sum Closest
    • 17. Letter Combinations of a Phone Number
    • 18. 4Sum
    • 19. Remove Nth Node From End of List
    • 20. Valid Parentheses
    • 21. Merge Two Sorted Lists
    • 22. Generate Parentheses
    • 23. Merge k Sorted Lists
    • 24. Swap Nodes in Pairs
    • 25. Reverse Nodes in k-Group
    • 26. Remove Duplicates from Sorted Array
    • 27. Remove Element
    • 28. Implement strStr()
    • 29. Divide Two Integers
    • 30. Substring with Concatenation of All Words
    • 31. Next Permutation
    • 32. Longest Valid Parentheses
    • 33. Search in Rotated Sorted Array
    • 34. Find First and Last Position of Element in Sorted Array
    • 35. Search Insert Position (Easy)
    • 36. Valid Sudoku
    • 37. Sudoku Solver
    • 38. Count and Say
    • 39. Combination Sum
    • 40. Combination Sum II
    • 41. First Missing Positive
    • 43. Multiply Strings
    • 45. Jump Game II
    • 46. Permutations (Medium)
    • 47. Permutations II (Medium)
    • 48. Rotate Image
    • 49. Group Anagrams
    • 50. Pow(x, n)
    • 51. N-Queens
    • 52. N-Queens II
    • 53. Maximum Subarray
    • 54. Spiral Matrix
    • 55. Jump Game
    • 56. Merge Intervals
    • 57. Insert Interval
    • 58. Length of Last Word
    • 59. Spiral Matrix II
    • 61. Rotate List
    • 62. Unique Paths
    • 63. Unique Paths II
    • 64. Minimum Path Sum
    • 66. Plus One
    • 67. Add Binary
    • 69. Sqrt(x)
    • 70. Climbing Stairs
    • 73. Set Matrix Zeroes
    • 74. Search a 2D Matrix
    • 75. Sort Colors
    • 76. Minimum Window Substring
    • 77. Combinations
    • 78. Subsets
    • 79. Word Search
    • 80. Remove Duplicates from Sorted Array II
    • 81. Search in Rotated Sorted Array II
    • 82. Remove Duplicates from Sorted List II
    • 83. Remove Duplicates from Sorted List
    • 84. Largest Rectangle in Histogram
    • 86. Partition List
    • 88. Merge Sorted Array
    • 89. Gray Code
    • 90. Subsets II
    • 92. Reverse Linked List II
    • 94. Binary Tree Inorder Traversal (Medium)
    • 95. Unique Binary Search Trees II
    • 96. Unique Binary Search Trees
    • 98. Validate Binary Search Tree
    • 100. Same Tree (Easy)
    • 101. Symmetric Tree
    • 102. Binary Tree Level Order Traversal
    • 103. Binary Tree Zigzag Level Order Traversal
    • 104. Maximum Depth of Binary Tree
    • 105. Construct Binary Tree from Preorder and Inorder Traversal
    • 106. Construct Binary Tree from Inorder and Postorder Traversal
    • 107. Binary Tree Level Order Traversal II (Easy)
    • 108. Convert Sorted Array to Binary Search Tree
    • 109. Convert Sorted List to Binary Search Tree
    • 110. Balanced Binary Tree
    • 111. Minimum Depth of Binary Tree
    • 112. Path Sum
    • 113. Path Sum II
    • 114. Flatten Binary Tree to Linked List
    • 116. Populating Next Right Pointers in Each Node
    • 117. Populating Next Right Pointers in Each Node IIㄟˋ大
    • 118. Pascal's Triangle
    • 119. Pascal's Triangle II
    • 120. Triangle
    • 121. Best Time to Buy and Sell Stock
    • 122. Best Time to Buy and Sell Stock II
    • 123. Best Time to Buy and Sell Stock III
    • 125. Valid Palindrome
    • 654. Maximum Binary Tree
    • 127. Word Ladder
    • 129. Sum Root to Leaf Numbers
    • 130. Surrounded Regions (Medium)
    • 131. Palindrome Partitioning
    • 133. Clone Graph
    • 134. Gas Station
    • 136. Single Number
    • 137. Single Number II
    • 138. Copy List with Random Pointer
    • 139. Word Break
    • 141. Linked List Cycle
    • 143. Reorder List
    • 144. Binary Tree Preorder Traversal
    • 145. Binary Tree Postorder Traversal
    • 147. Insertion Sort List
    • 148. Sort List
    • 151. Reverse Words in a String
    • 152. Maximum Product Subarray
    • 153. Find Minimum in Rotated Sorted Array
    • 154. Find Minimum in Rotated Sorted Array II
    • 155. Min Stack
    • 160. Intersection of Two Linked Lists
    • 164. Maximum Gap
    • 169. Majority Element (Easy)
    • 173. Binary Search Tree Iterator
    • 174. Dungeon Game (Hard)
    • 189. Rotate Array
    • 198. House Robber (Easy)
    • 199. Binary Tree Right Side View (Medium)
    • 203. Remove Linked List Elements
    • 206. Reverse Linked List
    • 213. House Robber II (Medium)
    • 215. Kth Largest Element in an Array (Medium)
    • 222. Count Complete Tree Nodes
    • 226. Invert Binary Tree
    • 230. Kth Smallest Element in a BST
    • 232. Implement Queue using Stacks
    • 234. Palindrome Linked List (Easy)
    • 235. Lowest Common Ancestor of a Binary Search Tree
    • 236. Lowest Common Ancestor of a Binary Tree
    • 237. Delete Node in a Linked List
    • 240. Search a 2D Matrix II
    • 242. Valid Anagram
    • 257. Binary Tree Paths
    • 283. Move Zeroes
    • 337. House Robber III (Medium)
    • 347. Top K Frequent Elements
    • 349. Intersection of Two Arrays
    • 409. Longest Palindrome (Easy)
    • 437. Path Sum III
    • 442. Find All Duplicates in an Array
    • 449. Serialize and Deserialize BST
    • 450. Delete Node in a BST
    • 543. Diameter of Binary Tree
    • 572. Subtree of Another Tree
    • 653. Two Sum IV - Input is a BST
    • 654. Maximum Binary Tree
    • 700. Search in a Binary Search Tree
    • 701. Insert into a Binary Search Tree
    • 783. Minimum Distance Between BST Nodes
    • 876.Middle of the Linked List
    • 942. DI String Match
  • Notes of algorithms
    • Binary Tree traversal
    • 廣度優先搜尋 (Breadth-first Search)
    • Divide and Conquer
    • Linked list: Insert Node
    • Dynamic programming
    • 深度優先搜尋 (Depth-first Search)
    • Lowest Common Ancestor (LCA)
    • Asymptotic notation
    • Binary search tree
    • AVL Tree (Height Balanced BST)
    • Linked list: Split the list
    • Linked list: Traverse the list
    • Linked list: Delete node
    • Heap sort
    • Cartesian tree
  • C++
Powered by GitBook
On this page
  • 1.定義
  • 2.算法
  1. Notes of algorithms

Lowest Common Ancestor (LCA)

Previous深度優先搜尋 (Depth-first Search)NextAsymptotic notation

Last updated 6 years ago

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