항해99 - 3주차, 가장 긴 동일 값의 경로

Today I learned
2022/01/25

회고록

---

1/25

항해 99, 알고리즘 2주차

교재 : 파이썬 알고리즘 인터뷰

이진트리

1. 이론

이진 트리(binary tree)의 정의

트리 중에서 가장 많이 쓰이는 트리가 이진트리이다. 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree) 라고 한다. 서브트리는 공집합일 수 있다. 따라서 이진트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고 모든 노드의 차수가 2 이하가 된다. (차수(degree)는 어떤 노드가 가지고 있는 자식 노드의 개수)

이진트리

공집합이거나
루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진트리의 서브트리들은 모두 이진트리여야 한다.

이진트리의 성질

n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 가진다. 그 이유는 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모노드를 가진다. 그리고 부모와 자식 간에는 정확하게 하나의 간선만이 존재한다.
높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2의h제곱 -1개의 노드를 가진다.

2. 문제

Given the root of a binary tree, return the length of the longest path, where each node in the path has the same value. This path may or may not pass through the root.

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

Input: root = [5,4,5,1,1,5]
Output: 2

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

3. MySol

• BinaryTree, DFS

from binary.prac import make_tree_by


def solution(binaryTreeList):

    root = make_tree_by(binaryTreeList, 0)

    dist = []
    result=0

    def dfs(node, level):
        if node is None:
            return 0

        left = dfs(node.left, level+1)
        right = dfs(node.right, level+1)

        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

        nonlocal result
        result = max(result, left + right)

        return max(left,right)

    dfs(root, 0)


    return result

if __name__ == '__main__':

    binTree = [5,4,5,1,1,None,5]

    result = solution(binTree)

    print('result : ' + str(result))

4. 배운 점

• 이진트리에 대한 이해
• DFS탐색구현 먼저 하고, 조건로직 구현
• 단계별로 나누어 접근

5. 총평

이진트리, DFS 훈련