【LeetCode】543. Diameter of Binary Treeを解く

問題へのリンク

問題概要

ある二分木rootを与えられたとき，その木の直径の長さを返す．

ここで，二分木の直径とは任意の2ノード間のパスの長さの中で最長のものを指す．

また，バスの長さとは2ノード間にある辺の数のことである．

例：

Input: root = [1,2,3,4,5]
Output: 3

制約

• 木のノードの数は$[1, 10^4]$である
• $-100 \leq Node.val \leq 100$

考えたこと

例えば例の入力を考える，

     1
   /   \
  2     3
 / \
4   5

このとき，最長の2ノード間のパスは以下のようになる：

     1
   /   \
  2     3
 /
4

従って，戻り値は3である．

次に，根が含まれない場合について考えてみる．

      1
     /
    2
   / \
  4   5
 /     \
6       7

このとき，最長の2ノード間のパスは以下のようになる：

    2
   / \
  4   5
 /     \
6       7

以上の実験から，あるノードに注目して左右の深さの合計が最も大きい時に解が得られると考えられる．

つまり，

1. ノードを全探索
2. 各ノードについて，左側の深さLと右側の深さRの合計L+Rを求める
3. 得られたL+Rのうち最大のものを戻り値とする

の手順で求めればいいといえる．

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0
        def depth(node):
            if node is None:
                return 0
            L = depth(node.left)
            R = depth(node.right)
            
            self.res = max(self.res, L+R)
            return 1 + max(L,R)
        
        depth(root)
        return self.res