[LeetCode#687] Longest Univalue Path

❒ Description

---

날짜	2024.09.21 (토)
레벨	Medium
제목	Longest Univalue Path
링크	https://leetcode.com/problems/longest-univalue-path/submissions/1397321235/
자료구조	트리
알고리즘	X
시간 복잡도	O(n)

 

543. Diameter of Binary Tree와 굉장히 유사한 문제이다.

 

 

 

 

 

❒ 문제 분석

---

부모-노드의 value와 자식-노드의 value가 동등한지를 판단하여야 하는 문제이다. 

이 문제 또한 재귀를 통해 Left, Right 자식 트리의 깊이를 파악함과 동시에 가장 긴 경로를 파악해야 한다.

위 그림에서 리프노드의 1과 1은 부모노드의 값인 4와 동일하지 못하기 때문에 문제의 요구사항에 충족하지 못한다.

 

 

 

 

 

❒ Solution

---

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public boolean isEqual(TreeNode node) {
        return node != null && val == node.val;
    }
}

int maxLenght = 0;
public int longestUnivaluePath(TreeNode root) {
    depth(root);
    return maxLength;
}

private int depth(TreeNode node) {
    int leftDepth = depth(node.left);
    int rightDepth = depth(node.right);
    
    // 부모노드의 val과 자식노드의 val이 동일한지 validation
    if (node.isEqual(node.left)) {
        leftDepth ++;
    } else {
        leftDepth = 0;
    }
    if (node.isEqual(node.right)) {
        rightDepth ++;
    } else {
        rightDepth = 0;
    }
    maxLength = Math.max(maxLength, leftDepth + rightDepth);
    return Math.max(leftDepth, rightDepth);
}

값이 동일한지 확인하는 로직은 TreeNode가 책임져야 하는 역할이기에 TreeNode에 isEqual 메소드를

작성하였다. 하지만 LeetCode에서는 해당 메소드를 알수 없기 때문에 통과되지 않는다.

 

 

 

 

 

---