LeetCode Problems解いた：1123. Lowest Common Ancestor of Deepest Leaves

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

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

| 例1　| 例2 | 例3 |
|:-:|:-:|:-:|
| ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/85457/05d995eb-c9bf-70a1-0c75-ba96c5372bee.png) |  ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/85457/c7a82e98-fa26-9cc0-3807-aad7e239606c.png) | ![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/85457/140a9afc-dee0-e6d9-5351-eeef9b80d9c2.png) |

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

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

</details>

## コード
今回はpythonでの記述。再帰関数だろうなーというところまでは思いついたが、そこから形にするのにとても時間がかかった。
<details>
<summary>コード全容</summary>

```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
        """
```

</details>

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

<details open>
<summary>処理の詳細フロー　(例)[3,5,1,6,2,0,8,null,7]</summary>
Step1:<br>
ノード3を親として、左のノード(ノード5)と右のノード(ノード1)の長さをdiggerで調べる。<br>
→ノード5側が長いので、ノード5へ(親をノード5に変更)。<br>
Step2:<br>
ノード5を親として、左のノード(ノード6)と右のノード(ノード2)の長さをdiggerで調べる。<br>
→ノード2側が長いので、ノード2へ(親をノード2に変更)。<br>
Step3:<br>
ノード2を親として、左のノード(ノード7)と右のノード(None)の長さをdiggerで調べる。<br>
→ノード7側が長いので、ノード7へ(親をノード7に変更)。<br>
Step4:<br>
ノード7を親として、左のノード(None)と右のノード(None)の長さをdiggerで調べる。<br>
→ノードの長さが同じなので、ノード7がLCAである。<br><br>

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

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/85457/c6fb9be1-60d8-26fc-0303-db01b89eb3f1.png)

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

</details>

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

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