# LeetCode Easy 235. Lowest Common Ancestor of a Binary Search Tree

tags: leetcode

問題

• Explore
• Problems

アイデア

BSTを与えられた時に，LCAを探せという問題です．

LCA(lower common ancestor)とはあるノードpとqが与えられたときに，pとqを子として持つ，もしくはそのノード自身として持つノードのことです．

解法

• LCAは自分，左部分木，右部分木のいずれかに2つでpもしくはqを持っています．
• それを求めるような関数を書きます

計算量

ノードの数を$N$，木の深さを$H$とします．

• 時間計算量
  • ノードを全て走査するので$O(N)$
• 空間計算量
  • 木の深さだけ再帰関数が深くなるので$O(H)$

Python

# 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':
        res = None
        def has_descendant(cur: 'TreeNode') -> bool:
            nonlocal res
            if not cur:
                return False
            is_on_mid = cur == p or cur == q
            is_on_left = has_descendant(cur.left)
            is_on_right = has_descendant(cur.right)
            if is_on_mid + is_on_left + is_on_right == 2:
                res = cur
            return is_on_mid or is_on_left or is_on_right
        has_descendant(root)
        return res