236.Lowest Common Ancestor of a Binary Tree

問題内容

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

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なら返された値が目的ノードである