説明:

これはLeetCodeのLongest Univalue Path題です.
これは,木が同じ値を持つときの最長パス長を求める問題である.この場合、「パス」とは、ノードが一緒に接続されなければならないため、パスの長さはこれらのノード間の幹線数です.
の問題では、上記の例に示すように、現在のツリーの同じ値の最長パスは、第1のノードから右側のサブノードのみに接続されたノード「5」へのパスであり、2本の幹線からなるため、2である.
ですが、パスは必ずしも最初の図のように直線ではありません.上図のように折り曲げてもパスを設定するだけで済むので、ルートノードでナビゲートするよりもエンドノードで逆方向にナビゲートするプールが考えられます.

に答える

基本的な考え方は、ツリー内のノードをエンドノードに再帰的に検索し、その2つのサブノードの現在のノードと同じ値のノードのUnivaluePathの長さを1だけ増やして更新することです.
例えば、の上の例と同様のツリーでは、左ノードを優先し、右ノード順にエンドノードを検索すると、1つのノードがパスを構成できないため、最長距離は0となる.
および再帰呼び出しが終了した後に親ノードに戻る場合、現在のノードを左、右の子ノードと比較して、Univalueの場合、Univalue Pathに幹線を追加し、パスの長さを増加させるという同じ値が得られる.
また、左側のサブノードから右側のサブノードまでのため、左側のサブノードのUnivaluePath距離と右側のサブノードのUnivaluePath距離とを加算し、最長距離値を更新する.この場合、上記距離2の4値ノードを有するUnivalue Pathが構築される.
次に、左側のサブノードまたは右側のサブノードのより長いUnivalue Pathを親ノードに渡す必要があります.これは木の高さを求めるのと似ていますが、親ノードは現在のノードと子ノードの値を比較し、同じ場合にのみUnivaluePathを継続するために戻り値を使用します.
上図では、左側のサブノードと右側のサブノードのUnivalue Pathの長さが同じであるため、任意のコンテンツを任意に返すことができるが、左側のサブノードのUnivalue Pathの長さが返されたと仮定すると、ルートノードは1を返す.ただし,ノード1はノード4と異なるため,Univalue Path計算(0とみなす)には適用されず,最長距離も更新されない.
このプロシージャをエンドノードからルートノードに再帰すると、最長の距離が得られます.これに基づいて実装されるコードは次のとおりです.

class Solution:
    # 재귀 함수에서 접근하기 위한 전역 변수.
    longestUnivalue = 0
    
    # 재귀 호출 함수.
    def findLongestUnivaluePath(self, node):
        # 말단 노드의 자식 노드라면 탐색 종료.
        if node is None:
            return None
        
        # 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 재귀 탐색.
        leftResult = self.findLongestUnivaluePath(node.left)
        rightResult = self.findLongestUnivaluePath(node.right)
        
        # 왼쪽 자식 노드와 현재 노드가 같은 값이라면 Univalue Path 길이 증가.
        # 같은 노드가 아니라면 Univalue Path가 끊긴 것이므로 길이 초기화.
        if node.left and node.left.val == node.val:
            leftResult += 1
        else:
            leftResult = 0
        # 오른쪽 자식 노드와 현재 노드가 같은 값이라면 Univalue Path 길이 증가.    
        # 역시 같은 노드가 아니라면 Univalue Path가 끊긴 것이므로 길이 초기화.
        if node.right and node.right.val == node.val:
            rightResult += 1
        else:
            rightResult = 0
        
        # 현재 노드까지 포함한 Univalue Path의 길이 갱신.
        # 위에서 경로가 끊겼다면 0으로 초기화했기 때문에 Univalue 조건 준수 가능.
        self.longestUnivalue = max(self.longestUnivalue, leftResult + rightResult)
        # 더 긴 Univalue Path의 길이를 반환.
        return max(leftResult, rightResult)
    
    
    def longestUnivaluePath(self, root: TreeNode) -> int:
        # 기본적인 예외처리.
        if root is None:
            return 0
        
        # 루트 노드부터 탐색 시작 및 최장거리 반환.
        self.findLongestUnivaluePath(root)
        return self.longestUnivalue

ポスト

応用して高い論理の解答を求めるのは印象的な問題です.UnivaluePathの概念を誤って理解していたので,経路に含まれるノードの個数で解答を作成し,幹線の個数であることを知り,それを分解して変更したのを覚えている.それ以外にも,現在のノード,2つのサブノードに接続されたUnivaluePathなど,考えるべき問題はたくさんある.