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