# LeetCode Medium 236. Lowest Common Ancestor of a Binary Tree

tags: leetcode

スクリプト言語ってろくな言語がないような気がするのは私だけでしょうか…

JS，Python，Shell script…Rubyがもっと海外で使われていればこうなっていなかったのか…

問題

• Explore
• Problems

アイデア

二分木を与えられた時，この木の2つのノードが与えられるのでその最も下の共通の祖先を探せという問題です．

注意点として，全てのノードの値は一意で与えられる2つのノードは異なるノードです．

解法

• 求めるようなノードはそのノード，左部分木，右部分木のうちいずれか2つがpもしくはqを持っています．
• そのため，再帰的に木を遡ってそのようなノードを探す関数を作ります(has_descendantという関数にしました)

計算量

ノードの数を$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
            has_on_cur = cur == p or cur == q
            has_on_left = has_descendant(cur.left)
            has_on_right = has_descendant(cur.right)
            if has_on_cur + has_on_left + has_on_right == 2:
                res = cur
            return has_on_cur or has_on_left or has_on_right
        
        has_descendant(root)
        return res