LeetCode 1000000本ノック【104. Maximum Depth of Binary Tree】

# 目次

|No.|項目|
|:----:|:-------------|
| 1 | [概要](#概要) |
| 2 | [問題](#問題) |
| 3 | [解法](#解法) |
| 4 | [メイキング](#メイキング) |

# 概要
<!-- 発端や概要を記載 -->
●発端
　・競プロ初心者、コーディング面接でズタボロにされ、
　・最低限のアルゴリズム学習とコーディング力強化を習慣化するため記事化
●環境
　・LeetCodeブラウザ上で実装（vscodeに拡張機能にするかもシレナイ）
　・言語はpython3
●その他ルール
　・google検索は自由に（直接的なLeetCodeの問題解説ページはNG）
　　（60分実装して実装出来なければ解説ページ参照）
　・[コーディング面接対策のために解きたいLeetCode 60問](https://1kohei1.com/leetcode/)から問題選出
　・「1000000」は任意の2進数とする


<!-- 各チャプター -->
# 問題
- [104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)


>Given the root of a binary tree, return its maximum depth.

>A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

⇨「バイナリツリーの深度を返してね。深度ってのはルートノードから
　リーフノードまでの最長距離パスのノード数だよ」と書いてます。知らんけど。

`ex1
Input: root = [3,9,20,null,null,15,7]
Output: 3
`

`ex2
Input: root = [1,null,2]
Output: 2
`

![tmp-tree.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/502026/3b80524a-73f7-c781-f0e9-46ab9e3c5592.jpeg)

※要は「一番深いとこまでのノード数」なので
　BTの概念さえ持っていれば要件自体はシンプル。

# 解法
実施時間：60分オーバー

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
      if not root:
        return 0
      
      return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
```



# メイキング

```Python
        #IF rootあるよ！
            #深度+1
            #leftあるよ！
                #深度+1
                #leftあるよ!
                    #...
                #Rightあるよ
                    #...
            #Rightあるよ！
                #...
```

いつも通り処理の仮コーディング。
お、これは得意な再帰処理のパターンですね（血涙）

```python
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
            depth = 0
            left_depth = 0
            right_depth = 0
            def branch_depth_check(root,left_depth,right_depth):
                #左枝があるならleft_depth+1
                if root.left:
                    left_depth += 1
                    branch_depth_check(root.left,left_depth,right_depth)
                #右枝があるならright_depth+1
                if root.right:
                    right_depth += 1
                    branch_depth_check(root.right,left_depth,right_depth)
                return max(left_depth,right_depth)
            #rootあるなら深度+1
            if root:
                #左右どちらかあるならとりあえず深度+1
                if root.left or root.right:
                    left_depth += 1
                    right_depth += 1
                depth += 1
                #左右確認
                depth = branch_depth_check(root,left_depth,right_depth)
            return depth
```

時間オーバー時のコードはこちら、テストケースに合わせて修正を繰り返していたら
いつの間にか無限モグラ叩きパターンに入ってしまっていて、正直心折れてました。

そしてこちら参照し速攻解決。
- [# LeetCode Easy 104. Maximum Depth of Binary Tree](https://propyon.hateblo.jp/entry/2020/01/26/000000)

こんなシンプルになるのか。。。
深さ優先探索の考え自体はあっていましたね。再帰処理も使ってますし（必死）

あぁ、再帰処理に苦手意識が芽生えそう。。。
下記のようなイメージ自体は付いているけども、脳のワークスペースが足りず
シミュレーションしきれないので、図解書きながらとかするしか無いのかなぁ。。。

http://lupus.is.kochi-u.ac.jp/~shiota/graphmovies/dfs-bt.html