1. 트리 자료구조란?
2. 이진 트리란?
이진트리는 컴퓨터 응용에서 가장 많이 활용되는 아주 중요한 트리구조이다. 이 이진 트리는 모든 노드가 정확하게 두 개의 서브트리를 가지고 있는 트리이다. 다만 서브트리는 공백이 될 수 있다. 즉 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽서브트리와 오른쪽 서브트리로 구성된다. 여기서 중요한점은 왼쪽과 오른쪽 서브트리를 확실하게 구분한다는 것이다.
출처: https://kingpodo.tistory.com/27 [킹포도의 코딩]
3. 트리노드의 구현
class TreeNode: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right
4. 트리를 생성 하는 함수
def make_tree_by(lst, idx): parent = None if idx < len(lst): value = lst[idx] if value == 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
5.문제
이진트리를 반전 시켜라!
6.풀이
class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: deq = deque([root]) while deq: cur = deq.popleft() if cur: fir = cur.left sec = cur.right cur.left = sec cur.right = fir deq.append(cur.left) deq.append(cur.right) return root
먼저 인자로 받은 트리구조를 큐 로 받아 온다음
첫번째 노드를 가져와서 해당 노드의 left 와 right 를 바꿔줍니다 .
그럼 현재 트리의 구조는 아래 구조 처럼 바뀐다.
지금 위치까지 왔으면 이제 마지막 각 리프의 순서를 바꿔줘야한다 .
현재 left 7과 right 2를 각각 deq 에 넣어준다
그다음 먼저 들어간 7의 노드에 접근 해서
left 6 과 right 9 의 위치를 변경 해주고
또 deq 에 넣어준다음 그다음 노드인 2에 접근 해서 left 1과 right 3을 바꿔준다.
그 다음 또 지금은 리프이지만 각 리프에 더 접근할수있는 숫자가 있는지 파악 하기 위해 위 설명과 같은 방식으로 자식 노드에 하나하나 다 접근을 해본다 지금 현재로서는 9631 이 마지막노드인 리프이기 때문에 여기서 탐색을 마친다.
