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 :

解題思路 :

• 這題可以拿來與 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
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!