출처 : 파이썬 알고리즘 인터뷰

오늘은 쉬운 문제 두 개를 풀어보았어요.

leetcode 687.Longest Univalue Path

트리에서 동일한 값이 연속으로 이어지는 가장 긴 경로의 길이를 반환하는 문제이다.

생각의 흐름

맨 끝으로 가서(리프노드)

-> 올라오면서 현재꺼랑 value 같으면 += 1

-> 양쪽의 값을 더한 값이 부모 노드의 상태값이 된다

접근 1

리프노드까지 내려가는 dfs

def dfs(node):
  if not node: return -1

	left = dfs(node.left)
  right = dfs(node.right)
  
  if node.left and node.left.val == node.val:
    left += 1
  else:
    left = 0
    
  if node.right and node.right.val == node.val:
    right += 1
  else:
    right = 0
    
    
  self.longest = max(self.longest, right+left)
  
  return max(right, left)

max를 이용해 현재 최장길이와 현재 부모노드의 상태값(왼쪽자식+오른쪽자식) 중 큰 것을 저장하는 것이 포인트

최종 코드

class Solution:
    result:int = 0
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
      def dfs(node):
        if not node : return -1
      
      	left = dfs(node.left)
        right = dfs(node.right)
        
        if node.left and node.left.val == node.val:
          left += 1
        else: left = 0
        
        if node.right and node.right.val == node.val:
          right += 1
        else: right = 0
        
        self.result = max(self.result, left+right)
        
        return max(left, right)
      
      dfs(root)
      
      return self.result

두번째 문제로 고고~

오늘의 두번째 문제

leetcode 226.Invert Binary Tree

이진 트리를 좌우로 뒤집은 형태로 바꿔주는 문제인데요~

생각보다 몹시 간단합니다

생각의 흐름

그냥 맨 밑으로 가서(리프노드)

-> 올라오면서 왼쪽 자식, 오른쪽 자식 스왑해주면 되지 않을까

접근 1

진짜 단순하게 dfs로 맨 밑까지 가서 올라오면서 스왑하는 구조로 작성

def dfs(node):
  if not node : return None
  left = dfs(node.left)
  right = dfs(node.right)
  
  node.left, node.right = right, left
  
  return node

이게 됩니다.

최종 코드

class Solution:
  def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
    def dfs(node):
      if not node: return None
    
    	left = dfs(node.left)
      right = dfs(node.right)
      
      node.left, node.right = right, left
      
      return node
    
    return dfs(root)