인프런 커뮤니티 질문&답변

안녕하세요 제환님.

해당 코드는 leetcode에 제출했을 때 작동되는 코드입니다. 그래서 leetcode에서는 해당 리스트가 트리 구조로 들어가게 될 거에요!

자신의 컴퓨터에서 코드를 디버깅 하고 싶다면 다음의 코드를 참고해보시길 바랄게요!!

from collections import deque


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


def array2tree(arr):
    q = deque()
    root = TreeNode(arr[0])
    q.append(root)

    idx = 1
    while idx < len(arr):
        cur_node = q.popleft()

        # left Node
        if arr[idx] != None:
            cur_node.left = TreeNode(arr[idx])
            q.append(cur_node.left)
        idx += 1

        # right Node
        if arr[idx] != None:
            cur_node.right = TreeNode(arr[idx])
            q.append(cur_node.right)
        idx += 1
    return root


def LCA(root, p, q):
    if root == None:
        return None

    left = LCA(root.left, p, q)
    right = LCA(root.right, p, q)
    if root.val == p or root.val == q: # root 가 아닌 root.val을 해줘야한다.
        return root.val
    elif left and right:
        return root.val
    return left or right

# 기존코드
# def LCA(root, p, q):
#     if root == None:
#         return None

#     left = LCA(root.left, p, q)
#     right = LCA(root.right, p, q)
#     if root == p or root == q:
#         return root
#     elif left and right:
#         return root
#     return left or right


root = array2tree([3, 5, 1, 6, 2, 0, 8, None, None, 7, 4])


print(LCA(root, 6, 4))

https://discord.com/channels/941959559759679559/1059823137753137192/1081108626938269776