題目

LeetCode - 235. Lowest Common Ancestor of a Binary Search Tree

解題思路

給定一個二元搜尋樹及其中兩個不同的節點,試找出它們的最近共同祖先(LCA)。

  • 注意: a node to be a descendant of itself 自己可以是自己的後裔

那麼,我們如何尋找這個最近共同祖先呢?
首先要知道,這是一棵二元搜尋樹,假設這個LCA的節點叫作L好了,
兩個節點分別叫p跟q,那麼我們可以考慮以下幾個狀況:

  1. 如果L是p或q其中之一的話,先遇到誰,就代表誰是那個LCA。
    (因為先遇到的節點會是後面的那個節點的祖先)
  2. 如果L不是p或q其中之一的話,L的値的範圍必在p.val和q.val之間,
    也就是說兩者會位在L的不同側的子樹。
    (即p.val < L.val < q.val或p.val > L.val > q.val)

如果從root開始判斷的話,就可以分成幾種情況:

  1. root的値和p或q的值相等 => 直接回傳root (p或q就是L)
  2. root的値在p和q的值的範圍之內 => 直接回傳root
    (即p.val < L.val < q.val或p.val > L.val > q.val)
  3. p和q的値都小於root的值 => 往下找root.left的狀況遞迴
  4. p和q的値都大於root的值 => 往下找root.right的狀況遞迴

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None

class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root == p: return root
if root == q: return root
if p.val < root.val and q.val < root.val:
return self.lowestCommonAncestor(root.left, p, q)
if root.val < p.val and root.val < q.val:
return self.lowestCommonAncestor(root.right, p, q)
return root

Reference