[LeetCode]687. Longest Univalue Path

Longest Univalue Path - LeetCode

2️⃣ 두번째 풀이

2022-02022

---

이진트리의 루트가 주어졌을 때, 가장 긴 path의 길이를 리턴하다. 이 때 path의 각 노드들은 모두 같은 값을 갖는 것들이어야 한다. (path는 root를 지날 수도, 지나지 않을 수도 있다 )

• path 의 길이 : 두 노드 사이의 edge의 개수

문제 풀이

(:30)

이 문제를 풀 때면, parent - child의 값이 같은 경우와 다른 경우를 먼저 나눠보게 된다.

또한, 먼저 leaf node에 도달할 때 까지 탐색을 하여, parent로 값을 리턴하는 식으로 문제를 푸는 방식을 생각할 수 있다.

이 때 주의할 것이 있는데

max 를 update 하는 값과, 상위로 리턴하는 값을 다르게 해야한다 ( 내 풀이식으로는)

• 상위노드로 리턴하는 값 : 현재노드의 left subtree, right subtree에서의 longest univalue path 값
• 현재 노드에서 max를 update 할 때 값은 : 현재 노드를 루트로 하는 서브트리에서의 longest univalue path 값.
• 즉, 상위노드로 리턴하는 값과 max 업데이트 값이 다르다는 것에 주의해야한다.

class Solution {
    public int max = 0 ; 
    public int longestUnivaluePath(TreeNode root) {
        if(root == null) return 0; 
        
        dfs(root,root.val);
        return max; 
    }

    
    public int dfs(TreeNode cur, int pv){
        if(cur == null) return 0;
        int left = dfs(cur.left,cur.val);
        int right = dfs(cur.right,cur.val);
        // update max
        max = Math.max(max,left+right);
        // return 
        if(cur.val == pv) return Math.max(left,right)+1;
        else return 0;
    }
}

1️⃣ 처음 풀 때

이진트리의 root가 주어졌을 때, “같은 값을 가진 노드로만 이루어진 가장 긴 경로” 의 길이를 리턴하라

• 두 노드 사이의 path의 길이는, 그 둘 사이의 엣지의 개수로 나타낸다.
• 노드의 개수는 최대 1만개

문제 풀이

(0:60)

책에는 별이 한개던데.. 한개짜리 문제가 맞는가 모르겠다

문제를 푸는데 몇 번 틀렸었음

• 그 이유는 dfs를 두번씩 하고 있었다 → 그에 따라 값이 바뀌어버렸었다. 이런.. 바보같다. 주의해야할 듯 💥

두 노드 사이의 길이

• 이 문제도 이진트리의 직경 문제처럼 구해야 한다.
  • 위 → 아래 로는 풀이를 쉽게 떠올릴 수가 없는 이유는, left + right subtree 에 대한 합산을 root 에서 진행을 해야하기 때문이다. 따라서 left subtree의 값 + right subtree의 값을 더해주는게 좋다.

path라는 것은 연속된 노드여야한다. 그리고 이 문제는 같은 값을 가진 노드들이어야 한다. 따라서, 하위노드가, 상위노드와 값이 다른 경우에는 그 연결이 끊어진 것이다

• → 상위노드로는 0 을 리턴하고 ( 상위노드에 대한 합산에 줄 값이 없는 것)
• → 현재노드를 서브트리의 루트노드로 한 것을 구하도록 한다.

상위노드와의 값이 같은 경우에만, depth를 리턴해줘야한다

트리의 직경 문제에서도 혼란이 조금 있었던 부분인데 여기서도 똑같은 행동을 하고 있었음.

class Solution {
    public int max = 0; 
    public int longestUnivaluePath(TreeNode root) {
        // 시작 val은 Node.val 범위에 없는 값을 주도록 한다. -> 그래야, root도 path의 루트인 경우에 대해서도 해 볼 수 있음 
        dfs(root,1001);
        return max;
    }
    // 계속 틀렸던 이유 -> dfs를 두번씩 하고 잇었음 -> 그에 따라 값이 바뀌어버림...
    // 현재노드 cur, 상위노드의 값 val 
    public int dfs(TreeNode cur, int val){
        if(cur == null) return 0;
        int left = dfs(cur.left,cur.val);
        int right = dfs(cur.right,cur.val);
	// max 를 update하고 ( 항상 현재 노드가 해당 경로의root노드(?) 가 될 가능성이 있기 때문임. ) 
        max = Math.max(max,left+right);

        if(cur.val!=val){
            // cur을 루트로 하는 path tree를 찾는다. 
            // 상위노드로 리턴하는 값은 0이어야함 ( 동일값이 아니었으니)
            return 0;
        }else{
							// 부모에게는 depth값을 리턴
            return Math.max(left,right)+1;
        }             
    }
}