[LeetCode] 687. Longest Univalue Path

😎풀이

1. dfs를 통한 깊이 우선 탐색
   1-1. leaf가 node와 동일한 값을 같는다면 길이에 추가
   1-2. 갱신은 leaf 길이의 합으로 가장 긴 길이를 갱신
   1-3. 단, 반환의 경우 두 길이를 합한 값이 아닌 root 에서 가장 멀리 떨어진 노드를 기준으로 반환하여 최장 길이 탐색이 가능하도록 함
2. 최장 단일 값의 길이 반환

function longestUnivaluePath(root: TreeNode | null): number {
    let longest = 0
    function dfs(node: TreeNode | null) {
        if(!node) return 0
        const left = dfs(node.left)
        const right = dfs(node.right)
        let leftLen = 0
        if(node.left && node.val === node.left.val) leftLen = left + 1
        let rightLen = 0
        if(node.right && node.val === node.right.val) rightLen = right + 1
        longest = Math.max(longest, leftLen + rightLen)
        return Math.max(leftLen, rightLen)
    }
    dfs(root)
    return longest
};