[Golang][Leetcode][BinaryTree]刷題系列-235-Lowest Common Ancestor of a Binary Search Tree

235. Lowest Common Ancestor of a Binary Search Tree
Level : Easy
原題連結 : Click
題目 :
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 :
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))
|
|
最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!