LeetcodeGrind75

Medium 235. Lowest Common Ancestor of a Binary Search Tree

In this blog I will share a solution to the Lowest Common Ancestor of a Binary Search Tree problem.

範例

範例 1

假設我們有以下的二元搜尋樹：

        6
       / \
      2   8
     / \ / \
    0  4 7  9
      / \
     3   5
  • 輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
  • 輸出: 6
  • 解釋: 節點 2 和節點 8 的最低共同父層級節點是 6，因為 6 是同時包含 2 和 8 的最小節點

解題思路

這題可以利用 二元搜尋樹（BST） 的特性來快速找到答案

什麼是二元搜尋樹（BST）？

  • 在 BST 中，每個節點的左子樹節點值都比它小，右子樹節點值都比它大
  • 這個特性讓我們可以很快地判斷應該往左邊還是右邊找

如何找到最低共同父層級？

  1. 從樹的根節點開始檢查
  2. 如果 p 和 q 的值都比當前節點小，那麼它們一定在左子樹，我們就往左邊找
  3. 如果 p 和 q 的值都比當前節點大，那麼它們一定在右子樹，我們就往右邊找
  4. 如果一個值比當前節點小，另一個值比當前節點大，或者其中一個值等於當前節點，那麼當前節點就是最低共同父層級

Last updated on

On this page

範例
範例 1
解題思路
什麼是二元搜尋樹（BST）？
如何找到最低共同父層級？