ゼロから始めるLeetCode Day26「94. Binary Tree Inorder Traversal」

概要

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

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

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

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

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

Leetcode

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

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day25「70. Climbing Stairs」
次回
ゼロから始めるLeetCode Day27「101. Symmetric Tree」

問題

543. Diameter of Binary Tree
難易度はeasy。
Top 100 Liked Questionsからの抜粋です。

二分木が与えられるので、その木の直径を返します。
なお、ここでの直径とは各ノード間の中で最も長い距離を行き来するような通路のことを指します。

Example:

Example:
Given a binary tree
          1
         / \
        2   3
       / \     
      4   5    
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

この場合だと4から3までいく場合と5から3までいくものの二つが最長であり、間にある枝の数が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: 44 ms, faster than 72.73% of Python3 online submissions for Diameter of Binary Tree.
# Memory Usage: 15.9 MB, less than 51.72% of Python3 online submissions for Diameter of Binary Tree.

基本的な流れは一般的な深さ優先探索のそれと一緒です。ただ、今回は長さを調べる必要があるので、そのための変数ansを用意し、計算を付け加えました。

割と過去の木の問題でも深さ優先探索ばかり書いているのでそろそろ幅優先探索とかも勉強しなきゃなぁと思います。
今日はもう遅いのでこれでお終いです、お疲れ様でした。

良さげな解答が他にあれば追記します。