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

꾸역꾸역 오늘도 dfs문제를 풀어본다..

오늘의 문제

leetcode 543.Diameter of Binary Tree

리스트로 입력받은 이진트리의 최대 길이를 반환하는 문제다.

생각의 흐름

node가 어떻게 생겼더라

class TreeNode:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

이렇게 생겼군.

-> 길이를 반환하는거면 양쪽 자식의 끝까지 내려가서 올라오면서 계산하는 방식을 써야겠다

-> dfs

접근 1

노드가 없을 때는 상태값에 -1 을 주기

if not node:
  return -1

접근 2

왼쪽 자식, 오른쪽 자식의 상태값으로부터 부모노드의 상태값을 계산

그림과 같이 왼쪽자식/오른쪽자식이 각각 그 자식들로부터 계산한 상태값을 마지막 부모노드(root)가 계산하면 됨

접근 3

DFS 설계

def dfs(node):
  if not node:
    return -1
  
  left = dfs(node.left)
  right = dfs(node.right)
  
  self.longest = max(self.longest, left+right+2)
  return max(left, right)+1

최종 코드

class Solution:
  longest = 0
  def diameterOfBinaryTree(self, root):
    def dfs(node):
      if not node:
        return -1
      
      left = dfs(node.left)
      right = dfs(node.right)
      
      self.longest = max(self.longest, left+right+2)
      return max(left, right)+1
    
    dfs(root)
    return self.longest