개발자가 되고 싶은 준개발자

문제 레벨 별로 다른 순서(왼쪽->오른쪽, 오른쪽->왼쪽)로 이진 트리(Binary Tree)를 순회하라. 풀이 쉬울 줄 알았는데 생각보다 통과하기가 어려웠다. 기본적인 알고리즘은 이전 포스트인 이진 트리를 BFS(너비 우선 탐색) 방식으로 레벨별로 순회하는 알고리즘과 비슷하다. (june-coder.tistory.com/16?category=913762) [LeetCode] 102. Binary Tree Level Order Traversal 풀이 및 코드 문제 트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다. 풀이 이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다. 트리의 루트부터 leaf까지 순� june-coder.tistory.c..

문제 트리를 level 순으로 순회하여 각 레벨 별 노드의 값을 리턴한다. 풀이 이 문제는 트리를 level 순으로 순회하는 문제이기 때문에 BFS(너비 우선 탐색)가 적합하다. 트리의 루트부터 leaf까지 순회를 하면서 한 레벨 씩 리스트에 담는다. 한 레벨 씩 리스트에 담기 위해서는 이전 레벨의 노드들의 리스트를 받아 해당 노들들의 left, right을 리스트에 넣으면 된다. 코드 # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class So..

문제 이진 트리가 주어질때, 중심을 기준으로 대칭인지를 결과로 리턴하라. 풀이 이 문제를 푸는 방법은 재귀(recursively)와 반복(iteratively) 2가지 방법이 있다. 우선 재귀로 푸는 방법을 살펴보자. 보통 Tree 문제를 재귀로 풀때에는 root를 확인하고, 왼쪽 서브트리와 오른쪽 서브트리를 확인하는 방식으로 구현한다. 이 문제도 똑같은 방법으로 해결 가능하다. 단, 주의할 점은 대칭임을 확인하기 위해서는 왼쪽 서브트리와 오른쪽 서브트리를 반대로 비교해야 한다. 즉 두 서브트리의 root가 같은지 확인하고, 왼쪽 서브트리의 left가 오른쪽 서브트리의 right가 같은지, 왼쪽 서브트리의 right이 오른쪽 서브트리의 leftt가 같은지 확인하면 된다. 같은 풀이를 iterative하게..