• Home
  • About
    • Yerim Oh photo

      Yerim Oh

      Happy and worthwhile day by day :)

    • Learn More
    • Email
    • LinkedIn
    • Instagram
    • Github
    • Youtube
  • Posts
    • All Posts
    • All Tags
  • Projects

[1001] (파이썬) leet code_543. Diameter of Binary Tree

31 Jan 2020

Reading time ~2 minutes

Table of Contents
  • 이진 트리의 직경
    • 문제
    • 문제 풀기 전 알고 갈 개념
    • 풀이과정
      • 1) 마지막 노드 찾기
      • 2) 마지막 노드에서 거를러 올라감
  • 전체 코드
  • 결과
  • 내가 헤맨 이유

이진 트리의 직경

난이도 | ★
리트코드 543

문제

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

image

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3is the length of the path [4,2,1,3] or [5,2,1,3].


Example 2:
Input: root = [1,2]
Output: 1
Constraints:

The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100

[전제]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:

문제 풀기 전 알고 갈 개념

  • DFS(깊이 우선 탐색)
  • 이진트리

풀이과정

풀이의 전체 과정부터 살펴보자

1) 재귀함수로 제일 마지막 노드를 찾는다

2) 마지막 노드에서 거를러 올라감

  • 존재하지 않는 노드: -1 이라는 값을 부여
    • 이유: 정 이진 트리 Full Binary Tree 가 아닌 대부분의 경우에는 존재하지 않는 자식 노드에 -1 을 부여해 페널티 부여
    • 상태값: 리프 노드에서 현재 노드까지의 거리
    • 거리(정답): 왼쪽 자식 노드의 상태값과 오른쪽 자식 노드의 상태값의 합에 2를 더한 값(없는 경우 양쪽에 -1을 부여하기 때문에)

1) 마지막 노드 찾기

def dfs(node: TreeNode) -> int:
  ...
  left = dfs(node.left) 
  right = dfs(node.right)

계속 재귀 호출을 통해 왼쪽, 오른쪽의 각 잎 노드까지 DFS로 탐색
image image

2) 마지막 노드에서 거를러 올라감

2개의 값 계산,

  • 거리(정답): 최종 결과가 될 가장 긴 경로 self.longest
    • left + right + 2
  • 상태값: 리프 노드에서 현재 노드까지의 거리
    • max(left, right) + 1

[방법]

  • 자식 노드가 하나도 없는 경우
    • left , right: 모두 -1
    • 거리: 0 (left+right+2 = -1+-1+2)
    • 상태값: 0 (max(left, right) + 1= -1+1=0)
  • 자식 노드가 모두 존재하는 경우, (자식 노드가 둘 다 상태값이 0 일 때)
    • 거리: 2 (left+right+2 = 0+0+2)
    • 상태값: 1 (max(left, right) + 1= 0+1=1)

이제 [4]-> [3]-> [2]-> [1]-> [결과] 순으로 탐방 할 것이다!!!

def dfs(node: TreeNode) -> int:
  ...
  self.longest = max(self.longest, left + right + 2) 
  return max(left, right) + 1

image image image image image


전체 코드

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    longest: int = 0
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(node: TreeNode)->int:
            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

결과

image


내가 헤맨 이유

재귀함수를 거꾸 쓰는 법을 잘 몰랐던것 같다

재귀함수를 거꾸로 쓰려면

def dfs(node: TreeNode) -> int:
  ...
  left = dfs(node.left) 
  right = dfs(node.right)
  
  ## 거꾸로 거슬러 올라가면서 하고싶은 코드

이렇게 짜면 호출했던 재귀함수다 마지막부터 실행코드를 실행한후 하나씩 없어지면서 백트레킹이 되는 것 같다!!!!!!

이제 머리에 새겨둬야겠다.. 흑…



Coding test Share Tweet +1