항해99 알고리즘 9회차

이진 트리의 최대 깊이 https://leetcode.com/problems/maximum-depth-of-binary-tree

Maximum Depth of Binary Tree - LeetCode

접근 방식

• 트리를 BFS로 탐색해서 depth를 찾는 해석 이였다.
• while, for문은 똑같다고 생각 했는데 이번거를 해석하면서 완전히 사라졌다.

 

맞은 결과 - 파이썬 알고리즘 인터뷰

# 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
import collections
from idlelib.tree import TreeNode
from typing import Optional


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:

        # root가 없으면 깊이는 0으로 처리
        if root is None:
            return 0

        # 큐 초기값을 root를 넣어줌
        queue = collections.deque([root])

        # 깊이를 확인할 변수
        depth = 0

        # 큐가 존재 하다면 반복
        while queue:

            # 깊이 더하기
            depth += 1

            # 현재 큐 길이 만큼 반복
            for _ in range(len(queue)):

                # 제일 앞에 있는 것을 뺀다.
                x = queue.popleft()

                # left가 존재 하면 추가
                # left부터 추가 하기에 순서는 BFS는 left부터 볼것임
                if x.left:
                    queue.append(x.left)

                # right가 존재 하면 추가
                if x.right:
                    queue.append(x.right)

        return depth

---

예상 대진표 https://programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

접근 방식

• 트리를 BFS로 탐색해서 depth를 찾는 해석 이였다.
• 벨로그 문제 해석
  • n 값으로 무엇을 하는 것 같은데 해석을 보면 a, b값으로 바로 결과가 나왔다.
  • n= 8, a = 4, b = 7 일 때 a, b가 만나는 라운드는 밑의 계산으로 나온다.
  • (파이썬 // 은 정수값의 몫이 나온다.)
    
    • 4+1 // 2 = 2
    • 7+1 // 2 = 4
      • 2+1 // 2 = 1
      • 4+1 // 2 = 2
        
        • 1+1 // 2 = 1
        • 2+1 // 2 = 1
  • a, b를 계속 나눠주면 1,1로 남고, 라운드를 계속 더 해주면 정답이 나온다.

 

맞은 결과 - 벨로그

def solution(n,a,b):
    answer = 0
    while a != b:
        a = (a+1) // 2
        b = (b+1) // 2
        answer += 1
    return answer

---

이진 트리의 직경 https://leetcode.com/problems/diameter-of-binary-tree

Diameter of Binary Tree - LeetCode

접근 방식

• 이진트리기 때문에 왼쪽부터 노드가 있을 것.
• 왼쪽, 오른쪽의 최대 길이를 합치면 되지 않을까?

분석 및 놓쳤던 점

 

• 왼쪽, 오른쪽의 큰값만 따라 가야했는데 큰값이 아니라 전체 간선 탐색을 계속 해서 감이 안잡혔었다.
• 재귀함수를 통해서 제일 큰값을 max로 구분해서 계속 다음으로 넘겨주더라
• dfs를 통해 접근을 해서 
  • 1 2 4 5 3 으로 스택 프레임에 쌓여서 3부터 나는 반환 하는 줄 알았다. 절대 아니였고
  • 1 2 4 5에서 4 5에서 리프 노드여서 반환 한다.
  • 0은 노드가 없으면 0으로 리턴 해주니깐 리프 노드에서는 0+0이다.
    • 4번 노드: 1 + max(0, 0) length = max(0, 0+0) = 0
    • 5번 노드: 1 + max(0, 0) length = max(0, 0+0) = 0
      • 2로 백트래킹
        • 2번 노드: 1 + max(1, 1) length = max(0, 1+1) = 2
          • 1로 백트래킹
            • 3번 노드: 1 + max(0, 0) length = max(2, 0+0)
              • 1로 백트래킹
                • 1번 노드: 1 + max(2, 1) length: = max(2, 2+1) = 3

• 1 2만 있을 경우도 있다. 
  • 1 2만 있다고 하면은
    • 2번 노드: 1 + max(0, 0) length = max(0, 0+0)
      • 1로 백트래킹
        • 오른쪽은 None이여서 0
          • 1번 노드: 1 + max(1, 0) = 2 length = max(0, 1+0) = 1
    length 변수가 없어도 될 것 같은데? 라고 생각 했는데 리턴 할 시에 무조건 1을 더 해줘야해서 필요했었다.

맞은 결과 - 릿코드 솔루션

class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        length = 0

        def dfs(start: Optional[TreeNode]) -> int:
            if start is None:
                return 0

            nonlocal length
            
            left = dfs(start.left)
            right = dfs(start.right)

            length = max(length, left + right)
            return 1 + max(left, right)
        
        dfs(root)
        return length

---

가장 긴 동일 값의 경로 https://leetcode.com/problems/longest-univalue-path

Longest Univalue Path - LeetCode

접근 방식

 

 

분석 및 놓쳤던 점

 

 

---

이진 트리 반전 https://leetcode.com/problems/invert-binary-tree

Invert Binary Tree - LeetCode

접근 방식

 

 

 

 

분석 및 놓쳤던 점

 

 

 

---

트리의 부모 찾기 https://www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

접근 방식

 

 

 

분석 및 놓쳤던 점