[백준] 9934번: 완전 이진 트리

whitehousechef·2023년 11월 4일
0

https://www.acmicpc.net/problem/9934

initial

So the question describes an inorder traversal from left->root->right.

So I was thinking of adding the level of nodes logic to the impl of this traversal until I drew the tree graph and found out that

1 6 4 3 5 2 7
^ ^ ^
m r m

The middle of the original list is the root (always) and if you divide the list each time, the mid point is the middle point (root of subtree)

So i figured out the pattern but I really didnt kno how to implement this. So I googled and this was a divide and conquer question.

Remember dfs and backtracking?https://velog.io/@whitehousechef/%EB%B0%B1%EC%A4%80-10819%EB%B2%88-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%B5%9C%EB%8C%80%EB%A1%9C
Whenever you have a range of choices, you can call dfs multiple times to fully traverse the possibilities. So let's divide the list into 2 and call dfs that searches the lower and upper half. The breaking condition would be if start==end, that means we are at leaf so we append them at respective level and return. Rmb return is needed for backtracking cuz if not it will continue to the other logic.

solution

import sys
input = sys.stdin.readline
from collections import defaultdict, deque
import math

h=int(input())
lst = list(map(int,input().split()))
ans = defaultdict(list)

def dfs(start,end,level):
    if start==end:
        ans[level].append(lst[start])
        return

    mid = (start+end) //2
    ans[level].append(lst[mid])
    dfs(start,mid-1,level+1)
    dfs(mid+1,end,level+1)

dfs(0,len(lst)-1,0)
for key in ans:
    print(*ans[key])

revisited jan 30th

yes so it is like the bracket question and after solving some leetcode tree questions, I kinda get it better now.

I managed to think of incrementing levels but i wanst gonna use start and end pointers but like the length of list to be sliced. If length is 1 then it is a leaf node, in which case we append it to the respective level. But this pointer way is better cuz slicing is ineff.

complexity

2^n cuz there are 2 choices - searching lower and upper half?
n space

NOPE this is a binary search so

The provided code performs a binary tree traversal and prints the nodes at each level. The time complexity of this code is O(n), where 'n' is the number of elements in the lst. This is because the code processes each element in the list exactly once.

Here's a breakdown of the code's complexity:

  1. The dfs function recursively divides the list in half at each level of the tree until it reaches a base case where the start and end indices are the same (i.e., a single element is processed). This division is done using binary search techniques, which ensures that each element is visited exactly once. The number of levels in the recursion is determined by the height of the binary tree, which is logarithmic in 'n' for a balanced binary tree.

  2. At each level of the binary tree, the dfs function appends the element at the midpoint of the current range to the ans dictionary, which groups elements by level.

  3. After the traversal, the code prints the elements at each level. The loop that iterates over the ans dictionary and prints the elements at each level has a time complexity of O(n) because it iterates over each element exactly once.

Overall, the time complexity of the code is dominated by the O(n) traversal of the lst, making it O(n) in total. The space complexity is also O(n) because the ans dictionary stores elements grouped by level, and in the worst case, each element in lst could belong to a different level.

0개의 댓글