99클럽 코테 스터디 15일차 TIL + Tree/Depth-First Search/Breadth-First Search/Binary Tree : reverse-odd-levels-of-binary-tree

문제

링크텍스트

풀이

from typing import Optional
from typing import List

from collections import deque

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def reverseOddLevels(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        # print('reverseOddLevels')
        q = deque()
        q.append([root])
        l = 0
        while True:
            tn_is = q.popleft()
            l += 1
            q0 = []
            for tn_i in tn_is:
                if not tn_i.left:
                    return root
                q0.append(tn_i.left)
                q0.append(tn_i.right)
            q.append(q0)
            if l % 2 == 1:
                v = []
                for i in q0:
                    v.append(i.val)
                i = len(v) - 1
                for qi in q0:
                    qi.val = v[i]
                    i -= 1
        return -1

class nt:
    def __init__(self, root0):
        self.n = len(root0)
        rs = []
        i0 = 0
        for i in range(self.n):
            if root0[i]:
                i0 += 1
            rs.append(TreeNode(root0[i]))
        self.n0 = i0
        i0 = 1
        for i in range(self.n):
            #if rs[i].val:
            if True:
                rs[i].left = rs[i0]
                rs[i].right = rs[i0+1]
                i0 += 2
            if i0 == self.n:
                break
        self.n1 = i0
        self.r = rs[0]
    def pr(self,r):
        print('pr')
        q = deque()
        q.append([r])
        a = []
        while True:
            xs = q.pop()
            q0 = []
            for x in xs:
                if not x:
                    print(a)
                    return 0
                a.append(x.val)
                q0.append(x.left)
                q0.append(x.right)
            q.append(q0)
        return -1
        
for i in range(3):
    print(f'test case: {i}')
    if i == 0:
        root = [2,3,5,8,13,21,34]
        Output = [2,5,3,8,13,21,34]
    if i == 1:
        root = [7,13,11]
        Output = [7,11,13]
    if i == 2:
        root = [0,1,2,0,0,0,0,1,1,1,1,2,2,2,2]
        Output = [0,2,1,0,0,0,0,2,2,2,2,1,1,1,1]

    nt_i = nt(root)
    sol = Solution()
    # a = sol.reverseOddLevels(root)
    a = sol.reverseOddLevels(nt_i.r)
    # print(a)
    nt_i.pr(nt_i.r)
    print(Output)            

• perfect: A binary tree is perfect if all parent nodes have two children and all leaves are on the same level.
• level: The level of a node is the number of edges along the path between it and the root node.

• q에는 해당 level의 TreeNode 들을 넣습니다.
• 우선 q에 [root]를 넣고, level, l = 0으로 초기화를 합니다.
• 그리고 while True: 로 반복하며,
  • 해당 level, l이 홀수인 경우에, TreeNode 들의 값을 list, v에 넣습니다.
  • 그리고 각 TreeNode에 v를 역순으로 넣습니다.
  • 이번 문제의 tree는 perfect하기 때문에, None이면 변경된 tree, root를 반환하고 종료합니다.

test case: 0
pr
[2, 5, 3, 8, 13, 21, 34]
[2, 5, 3, 8, 13, 21, 34]
test case: 1
pr
[7, 11, 13]
[7, 11, 13]
test case: 2
pr
[0, 2, 1, 0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1]
[0, 2, 1, 0, 0, 0, 0, 2, 2, 2, 2, 1, 1, 1, 1]

• 위의 test 결과를 보시면, 3 test cases 모두 맞는 것을 알 수 있습니다.

결과