ゼロから始めるLeetCode Day7 「104. Maximum Depth of Binary Tree」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day6 「1342. Number of Steps to Reduce a Number to Zero」
次回
ゼロから始めるLeetCode Day7 「104. Maximum Depth of Binary Tree」

問題

104. Maximum Depth of Binary Tree

かなり初期の問題ですが、二分木の構造を理解する上で良い問題だと感じました。

二分木が与えられるのでその深さの最大値を探し出すようなアルゴリズムを書くことを求められます。

example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
return its depth = 3.
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        depth = 0
        stack = [(root,1)]
        
        while stack:
            root,length = stack.pop()
            if not root:
                return 0
            
            if length > depth:
                depth = length
            if root.right:
                stack.append((root.right,length + 1))
            if root.left:
                stack.append((root.left,length + 1))
        return depth
# Runtime: 40 ms, faster than 70.51% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 14.9 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.

以前の二分探索木に関する問題、ゼロから始めるLeetCode Day4 「938. Range Sum of BST」でも書いたような深さ優先探索で書いてみました。

Discussなどで調べてみて知ったのですが、こういう書き方もあるんですね。

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

from collections import deque

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        queue = deque([(root, 1)])
        while queue:
            curr, val = queue.popleft()
            if not curr.left and not curr.right and not queue:
                return val
            if curr.left:
                queue.append((curr.left, val+1))
            if curr.right:
                queue.append((curr.right, val+1))
# Runtime: 36 ms, faster than 89.87% of Python3 online submissions for Maximum Depth of Binary Tree.
# Memory Usage: 15 MB, less than 90.62% of Python3 online submissions for Maximum Depth of Binary Tree.

dequeを使って実装してあります。

Deque とは、スタックとキューを一般化したものです (この名前は「デック」と発音され、これは「double-ended queue」の省略形です)。Deque はどちらの側からも append と pop が可能で、スレッドセーフでメモリ効率がよく、どちらの方向からもおよそ O(1) のパフォーマンスで実行できます。

とあるように速いです。実際にRuntimeに関しても他の回答に比べて速いですね。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話

自作のChrome Extensionをインポートした時に "Invalid value for 'content_scripts[0].matches[0]': Empty path."というエラーが出たので解決した