Leetcode 543. Diameter of Binary Tree

Problem

この問題は、バイナリツリーにおける直径（ツリー内の任意の二つのノードを結ぶ最長のパス）の長さを求めるものです。ここでのパスとは、2つのノード間のエッジ（ノードを結ぶ線）の数を指します。

Given the root of a binary tree, return the length of the diameter of the tree.

InputとOutputの例は次になります。

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Key Idea

深さ優先探索（DFS) を使用します。これは、各ノードで左と右のサブツリーの深さ（最も深いところまでのエッジの数）を計算し、これらを合計します。そして、現在の直径（最長のパス）とこれらの深さの合計とを比較し、長い方を新しい直径とします。

しかし、深さを計算する際、それぞれのノードで再度左と右のサブツリーを探索すると効率が悪くなります。そのため、この問題では "Post-Order Traversal" と呼ばれる手法を使います。これはバイナリツリーを探索する方法の一つで、子ノードを親ノードよりも先に訪れる方式を指します。

Approach

葉ノードから順に、depthとdiameterという２つのパラメータを考えて行きます。
depthは、そのノードから葉ノードまでの最長の長さを表します。
左のサブツリーのdepthか右のサブツリーのdepthのどちらか長い方に1を足した値がdepthとなります。

diameterは、問題文中にもあるようにツリー内の任意の2つのノード間の最長パスの長さです。
ここで、diameterを考える際に、２つパターンがあります。
それは、(1) 該当ノードを通る経路が最長経路である場合と (2)該当ノードを通らない経路が最長経路の場合 です。

下記の画像中のグラフの場合で説明します。
(1) 該当ノードを通る経路が最長経路である場合
2 のノードの場合は、左のサブツリーの diameter : 2 と右のサブツリーの diameter : 1 を足した 3 がdiameter になります
(2) 該当ノードを通らない経路が最長経路の場合
1 のノードの場合は、右のノードを持たないので、左のサブツリーの diameter : 5 がdiameter になります
どちらのパターンに該当するかどうかは、「左のサブツリーのdepthと右のサブツリーのdepthの和」か「そのノード配下でメモした diameter 」のどちらが大きいかによって判断されます。

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:


        self.diameter = 0

        def depth(root):
            if root is None:
                return 0       
            left_depth =  depth(root.left) 
            right_depth =  depth(root.right) 

            # そのノードを通る方が最長の場合とそのノードを通らない方が最長の場合の両方存在
            self.diameter = max(self.diameter, left_depth + right_depth)
            return max(left_depth, right_depth) + 1

        depth(root)
        return self.diameter

Complexity

この解法では、計算量は下記の様になります。

• Time complexity: O(n)。このプログラムはバイナリツリーのすべてのノードを一度ずつ訪れます。各ノードでは、ノードの深さを計算するために定数時間の操作（深さの比較と加算）が行われます。ここでnはツリーのノード数です。

• Space complexity: O(n)。このプログラムは深さ優先探索を用いているため、スペース計算量はツリーの高さに比例します。最悪の場合（つまりツリーが線形リストのようになっている場合）、Space complexityはO(n)となります。しかし、ツリーが完全にバランスが取れている場合、Space complexityはO(log n)となります。

Reference