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

目次

No.	項目
1	概要
2	問題
3	解法
4	メイキング

概要

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

問題

• 104. 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

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

解法

実施時間：60分オーバー

# 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

メイキング

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

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

# 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

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

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