問題内容

入力される２つの数字に共通する祖先のうち最も近い層にある祖先を探すプログラムを書く

sample

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        
        l = self.lowestCommonAncestor(root.left, p, q)
        r = self.lowestCommonAncestor(root.right, p, q)

        if l and r:
            return root
        return l or r

ポイント

再帰的に呼び出すことで目的のノードが出力されるようにする
各点の呼び出しで最初にrootがNone、p、qのいずれに当てはまるかをチェックする
左右のサブツリーに目的ノードがあるか調べるために再帰呼び出し
lとrの両方から値が帰ってくれば、その親ノードが目的ノード
片方から値が返され、もう片方がNoneなら返された値が目的ノードである