Contents

[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 :

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
}

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