Lowest Common Ancestor of a Binary Search Tree

# 問題

二分探索木rootとその木に含まれる2頂点p/qが与えられる．pとqの共通の先祖のうち，高さが最も低いもの（最小共通祖先：Lowest Common Ancestor）を計算せよ．

# 解法

二分探索木は

左の子 ≤ 親 ≤ 右の子

が成立している．

rootがpとqの間にあれば最小木共通先祖はrootになる．さかのぼっていけばrootにぶつかるので，当たり前といえば当たり前．rootの手前で共通先祖が存在するかもしれないが，求めたいのは最小のものであることに注意．

再帰関数で書く解法がこちら．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
# 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.val < p.val and root.val < q.val:
            return self.lowestCommonAncestor(root.right, p, q)
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        return root

currというポインタを持ち出して繰り返しで書き下すと次のように書ける．

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

# 出典

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/