LeetCodeの問題集、1123. Lowest Common Ancestor of Deepest Leavesがacceptされたので、備忘録として。

概要

一番深い階層にいるノード(たち)の一番近い共通の親を探索する問題。
問題文では子を持たないノードをleafと呼ぶ、と書いてある。
また、この一番近い共通の親、というのをLowest Common Ancestor(最小共通祖先；LCA)と呼ぶらしい。
みんなこんなのどこで知るんだ...

例えば…

例1	例2	例3

例1：
一番深い葉っぱは、４階層目にある7と4。この二つを上に辿っていくと、最初にぶつかるのが2のノード。つまり、7と4のLCAは2となる。
例2：
一番深い葉っぱは、４階層目にある7、4、9。この3つを上にたどっていくと、最初にぶつかるのが3のノード。つまり、7と4と9のLCAは3となる。
例3：
一番深い葉っぱは、7のみ。この場合、LCAは7自身になる。

一番深い葉っぱが一つのみの場合は、それがLCAとなる。

コード

今回はpythonでの記述。再帰関数だろうなーというところまでは思いついたが、そこから形にするのにとても時間がかかった。

コード全容

Solution.py

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

# rootから始まるノードが、どれだけの深さを持つか調べる関数。 
# dig、というよりは最下層から登ってくる感じ
def digger(root):
        a = 1 if root.left is None else 1 + digger(root.left)
        b = 1 if root.right is None else 1 + digger(root.right)
        return max([a,b])　# 左と右で長かった方をもらって値を返す。

class Solution(object):        
    def lcaDeepestLeaves(self, root):
        # ノード直下の左と右の長さを見比べている。
        a = 0 if root.left is None else digger(root.left)
        b = 0 if root.right is None else digger(root.right)
        
        # 長さが違えば、長い方の子供に移り、それを親とする。
        # 同じ長さなら、このノードが共通祖先ということなので、自分を返して終了。
        if a > b:
            return self.lcaDeepestLeaves(root.left)
        elif a < b:
            return self.lcaDeepestLeaves(root.right)
        else:
            return root
        
        """
        :type root: TreeNode
        :rtype: TreeNode
        """

考え方

考え方の概要としては、

あるノードの左と右の長さを調べる(それがdigger)
あるノードからぶら下がっている左と右の長さが同じなら、それがLCA
長さが違うのなら、長い方の子供にLCAがいるはず！
長い方の子供を親とする
〜以下繰り返し〜

処理の詳細フロー　(例)[3,5,1,6,2,0,8,null,7]

Step1:
ノード3を親として、左のノード(ノード5)と右のノード(ノード1)の長さをdiggerで調べる。
→ノード5側が長いので、ノード5へ(親をノード5に変更)。
Step2:
ノード5を親として、左のノード(ノード6)と右のノード(ノード2)の長さをdiggerで調べる。
→ノード2側が長いので、ノード2へ(親をノード2に変更)。
Step3:
ノード2を親として、左のノード(ノード7)と右のノード(None)の長さをdiggerで調べる。
→ノード7側が長いので、ノード7へ(親をノード7に変更)。
Step4:
ノード7を親として、左のノード(None)と右のノード(None)の長さをdiggerで調べる。
→ノードの長さが同じなので、ノード7がLCAである。

また、各ステップ使用しているdiggerの動作イメージは以下。

diggerにせよメインメソッドにせよ、大元のノードを入れるだけで全探索してくれるので、再帰関数は使いこなせれば非常に強い味方である。

自分の結果

計算速度：上から数えて約30%ぐらい？
メモリ使用量：上から数えて30%ぐらい
ちょいコスパいいかな？ぐらいな感じ。

備考

調べると、LCAについてたくさん出てくる。
当たり前のように書かれているが、自分の知らない分野すぎてポカン。
きっと簡単な方なんだろうなぁ。と解き終わって感じた。
再帰関数の中に再帰関数が入っている。もうすこしカッコよく書けそうな気がする。