[항해99] 트리

트리 ? 

트리는 나무를 거꾸로 세워놓은 것처럼 보이는 계층형 비선형 자료구조 입니다.

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

 

트리에서 나오는 용어

노드 : 트리에서 데이터를 저장하는 기본 요소

루트 : 트리 맨 위에 있는 노드

레벨 : 최상위 노드를 레벨 0으로 하였을 때, 하위 branch로 연결된 노드의 깊이를 나타냄

부모 : 어떤 노드의 상위 레벨에 연결된 노드

자식 : 어떤 노드의 하위 레벨에 연결된 노드

리프 : 자식노드가 하나도 없는 노드

형제 : 동일한 부모를 가진 노드

깊이 : 트리에서 노드가 가질 수 있는 최대 레벨

 

완전 이진 트리

이진 트리 : 각 노드가 최대 두개의 자식을 가지는 트리

완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례로 삽입되어있음! 

 

힙이랑 다른 점은 완전 이진트리는 배열은 안 되어있다! 라는게 차이가 있음

힙은 최대힙이면 루트가 제일 크고, 자식 노드로 가면 숫자가 작아지고, 최소 힙이면 루트가 제일 작고, 자식으로 갈 수록 노드의 밸류값이 점점 커지는데, 이런 제약 사항이 없으!

예상 대진표

https://school.programmers.co.kr/learn/courses/30/lessons/12985

프로그래머스

트리 문제로 나왔지만, 트리로 꼭 풀지 않아도 괜찮다. 

트리 구조를 이해했다면 다음 라운드로 넘어간다면 크기가 반쪽짜리 배열이 되고, 인덱스도 반으로 준다는 것을 이용하면 된다! 

두 숫자 a,b의 인덱스가 같아지는 순간의 라운드를 리턴하면 답이 나온다. 

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

이진트리의 직경

https://leetcode.com/problems/diameter-of-binary-tree/

Diameter of Binary Tree - LeetCode

처음에는 무조건 루트노드를 거쳐가는 것이 제일 길 거라고 생각했었으나, 반례가 있었다. 

루트의 왼쪽 높이랑 오른쪽 높이를 더하면 안되는 이유는 한쪽 노드에서만 거리를 탐색했을 때 제일 긴 경우가 나올 수도 있기 때문이다.

루트노드에서 왼쪽 리프노드까지 거리는 4, 오른쪽 리프노드의 거리는 1이지만, 2번노드에서 왼쪽 리프노드까지 거리는 3, 오른쪽 리프노드까지 거리는 3으로 합이 6으로 5보다 크다

직경을 나타내는 diameter라는 변수를 잡고, 재귀적으로로 직경을 계산해서 크면 갱신하는 형태로 계산해주었다. 

# Definition for a binary tree node.
from typing import Optional


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


class Solution:
    def __init__(self):
        self.diameter = 0

    def depth(self, node: Optional[TreeNode]) -> int:

        left = self.depth(node.left) if node.left else 0
        right = self.depth(node.right) if node.right else 0

        if left + right > self.diameter:
            self.diameter = left + right

        return 1 + max(left, right)


    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        self.depth(root)
        return self.diameter

Longest Univalue Path

https://leetcode.com/problems/longest-univalue-path/

Longest Univalue Path - LeetCode

트리를 돌면서 같은 값을 가진게 얼마나 많이 연속되는지를 구하는 문제.

문제 조건에 같은 값을 가지는 구간은 루트노드를 통과하지 않는다 라는 조건 덕에 쪼오끔 더 편하다. 루트 기준 왼쪽 또는 오른쪽의 값만 구해서 max함수를 이용하면 되기 때문!

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
        
        
class Solution:
    
    def longestUnivaluePath(self, root: TreeNode) -> int:

        def dfs(node):
            
            nonlocal ans
            if not node: return 0
            lx, rx = dfs(node.left), dfs(node.right)
            if not node.left or node.left.val != node.val: lx = 0
            if not node.right or node.right.val != node.val: rx = 0
            ans = max(ans, 1 + lx + rx)
            return 1 + max(lx, rx)

        ans = 0
        dfs(root)
        return max(0, ans - 1)

트리의 반전

https://leetcode.com/problems/invert-binary-tree/

Invert Binary Tree - LeetCode

트리를 중앙 루트 기준으로 완전 반전시키면 되는 문제다.

트리는 이제 보니, 어떻게 재귀를 잘 돌리는지가 꽤나 많이 쓰이는 로직인듯...! 

이번에도 왼쪽 오른쪽에 대해서 자식노드의 왼쪽 오른쪽을 바꾸는 것을 재귀적으로 구현하면 된다.

# 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 invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return None
        
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        
        return root