Contents

# 235. Lowest Common Ancestor of a Binary Search Tree

## 題目 :

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

### Example :

Note

Example 1:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6.

Example 2:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Example 3:

Input: root = [2,1], p = 2, q = 1 Output: 2

#### 解題思路 :

• 這題可以拿來與 leetcode236做比較，可以大大的發現BST Search Operation的強大與便捷

• 這題就是需要你用BST的特性去做搜尋出特定兩node的最低共同祖先

• 只需要判斷兩node是否在同邊，若在同邊就往那邊繼續搜尋，若不同邊代表該node就是他們的最低共同祖先

• BST若用inorder遍歷就會形成一個由小到大的有序排列，利用這個特性這題會變得非常簡單
• 相當於在一個由小到大排序的數組中找出出現頻率最高的數字們

### Recursive解法

• time complexity: O(log(n)) , space complexity: O(1)
• 為何是log(n)呢? 由於他是BST，本身Search Operation就是O(log(n))，然而此題解題其實就是一般的Search Operation，故為O(log(n))

Runtime: 20 ms, faster than 63.37% of Go online submissions for Lowest Common Ancestor of a Binary Search Tree. (這邊不用太過在意執行時間，因為這題較為容易大家的執行速度都差不多，故%數不會太高，只用在意是否為O(log(n))

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 `````` ``````/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode { if root.Val > p.Val && root.Val > q.Val { return lowestCommonAncestor(root.Left, p, q) } if root.Val < p.Val && root.Val < q.Val { return lowestCommonAncestor(root.Right, p, q) } return root } ``````