이진 트리

트리는 바로 비선형 구조입니다!

비선형 구조는 선형구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어있습니다.

선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 많습니다!

선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고,

비선형구조는 표현에 초점이 맞춰져 있습니다.

높이가 h 일 때 최대 노드의 개수는 2^(h+1) - 1개 입니다.

그러면 이 때 최대 노드의 개수가 N이라면

N = 2^(h+1) - 1
→
h = log_2(N+1)-1

라고 할 수 있습니다!
즉! 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 log_2(N+1) - 1이므로

이진 트리의 높이는 최대로 해봤자 O(log(N))이 구나! 라고 말씀하시면 됩니다.

---

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


def make_tree_by(lst, idx):
    parent = None
    if idx < len(lst):
        value = lst[idx]
        if value is None:
            return

        parent = TreeNode(value)
        parent.left = make_tree_by(lst, 2 * idx + 1)
        parent.right = make_tree_by(lst, 2 * idx + 2)

    return parent