ゼロから始めるLeetCode Day44「543. Diameter of Binary Tree」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day43「5. Longest Palindromic Substring」
次回
ゼロから始めるLeetCode Day45 「1379. Find a Corresponding Node of a Binary Tree in a Clone of That Tree」

Twitterやってます。

問題

543. Diameter of Binary Tree

難易度はeasy。
Top 100 Liked Questionsからの抜粋です。

解いていたのに記事を書くのを忘れていたのを見つけたので書きます！

問題としては、二分木が与えられます。
その木の直径を調べ、二点間のノードの最も長い経路の長さを返すようなアルゴリズムを設計する、というものです。

          1
         / \
        2   3
       / \     
      4   5   

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

この場合は3が返されるとなっていますね。

解説

# 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 diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.ans = 0
        
        def dfs(node):
            if not node:
                return 0
            right = dfs(node.right)
            left = dfs(node.left)
            self.ans = max(self.ans,left+right)
            return max(left,right) + 1
    
        dfs(root)
        return self.ans
# Runtime: 40 ms, faster than 89.86% of Python3 online submissions for Diameter of Binary Tree.
# Memory Usage: 16 MB, less than 34.48% of Python3 online submissions for Diameter of Binary Tree.

深さ優先探索で深さを測り、直径なので最終的に親を経由するので+1をすれば解けます。

木の構造を理解できてれば比較的すんなり実装できるかと思います。

地味にてこずったとはいえない・・・

今回はここまで。お疲れ様でした！