2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Posted at

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

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

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

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day43「5. Longest Palindromic Substring」

今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

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をすれば解けます。

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

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

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

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?