題目:

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

給定一個binary search tree和其中兩個Node,找出兩個Node的最近共同祖先

這題我一開始沒注意到是binary search tree,結果就當普通的binary tree去做了
沒利用到binary search tree的性質當然會慢上許多
不過可以用在一般binary tree上我就分享一下吧

# 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 not root:
            return 0
        l=self.lowestCommonAncestor(root.left,p,q)
        r=self.lowestCommonAncestor(root.right,p,q)
        
        if l not in [0,1]:
            return l
        if r not in [0,1]:
            return r
        cnt=0
        if root==p or root==q:
            cnt=1 
        if cnt+l+r==2:
            return root
        else:
            return cnt+l+r

我是用計數器+遞迴的方式去實作
一旦遇到目標節點,計數器就加1
而計數器計到2時,就不再回傳計數器的值,而是回傳讓計數器變為2的節點(最近共同祖先)
最後執行時間104ms(faster than 66.72%)

用了binary search tree的性質,這題會輕鬆許多

# 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':
        while True:
            if root.val<q.val and root.val<p.val:
                root=root.right
            elif root.val>q.val and root.val>p.val:
                root=root.left
            else:
                return root

binary search tree性質:
左子樹上所有節點的值均小於它的根節點的值,右子樹上所有節點的值均大於它的根節點的值

藉此性質,我們的搜索會輕鬆許多
由上往下搜索
若root的值小於兩個目標節點(表示此節點非最近共同祖先),就向右搜索
若root的值大於兩個目標節點(表示此節點非最近共同祖先),就向左搜索
而當root的值介於兩個目標節點之間,則代表我們找到了最近共同祖先
直接回傳即可
最後執行時間82ms(faster than 92.73%)

那我們下題見