2021-01-29] Vertical Order Traversal of a Binary Tree

오늘의 문제:

leetcode.com/explore/challenge/card/january-leetcoding-challenge-2021/583/week-5-january-29th-january-31st/3621/

Explore - LeetCode

 

후.. Hard하다 Hard해.. ㅋㅋㅋㅋ 이번문제는 분류가 Hard여서 그런가 고려해야할 상황이 많았다..

 

문제 예시를 보면서 이해해보자.

 

배열로 주어지는 이진 트리에 대해서 왼쪽에서부터 위치한 내용에 따라 같은 위치면 같은 List로 표현한 내용을 반환

 

여기서 코드를 생각할 때 중요한 점이 2개 있었다.

 

1) 같은 위치에 있더라도 깊이에 따라 순서를 정렬한다.

2) 같은 위치, 같은 깊이라면 값으로 순서를 정렬한다. 

 

즉 position > depth > value  순으로 정렬 기준을 맞춘다.

 

주어지는 root를 (0,0)으로 가정하고

postion값은 왼쪽으로 가면 -1, 오른쪽으로 가면 +1

depth 값은 들어갈수록 +1로 가정하고 문제를 풀어본다.

 

ans=dict()
pos=0
dep=0
Traversal(root,pos,dep,ans) #Traversal 함수필요

Traversal 함수의 경우

 

node의 leaf ( left, right )가 있으면, 재귀적으로 호출하여 값을 추가해준다.

 

def Traversal(node:TreeNode,position:int,depth:int, ans:dict):
    if position in ans.keys(): # 이미 같은 position에 존재하는 값이 있다면 
        if depth in ans[position].keys(): # 같은 position, 같은 depth인지 검사
            ans[position][depth].append(node.val)
            ans[position][depth]=sorted(ans[position][depth]) # depth까지 같으면 value값으로 sort
        else:
            ans[position][depth]=[node.val] depth가 없다면, depth까지 추가.
    else:
        ans[position]={depth:[node.val]} # 최초의 position 값인 경우 바로 추가
    
    if node.left: # 왼쪽으로 가니 postion-1, depth+1 
        Traversal(node.left,position-1,depth+1,ans)
    if node.right: # 오른쪽으로 가니 postion+1, depth+1
        Traversal(node.right,position+1,depth+1,ans)

 

모든 값이 ans에 들어가지만, 한번 더 정제가 필요한 일이 있다.

그것은 position, depth는 dictionary의 key값으로 만들어져, 추가될때 순서를 상관하지 않았기 때문에 다시 정렬이 필요.

 

for i in sorted(ans.keys()): # sorted 함수로 position 정렬 ( 맨 왼쪽부터 오른쪽까지 )
    temp=[]
    for j in sorted(ans[i].keys()): # 같은 postion내 depth를 정렬 ( root에 가까운 순서대로 정렬 )
        temp.extend(ans[i][j]) # value의 경우 이미 위의 Traversal 함수에서 정렬되어있다.
    ret.append(temp)

 

최종 구현한 코드는 아래와 같다.

 

# 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
def Traversal(node:TreeNode,position:int,depth:int, ans:dict):
    if position in ans.keys():
        if depth in ans[position].keys():
            ans[position][depth].append(node.val)
            ans[position][depth]=sorted(ans[position][depth])
        else:
            ans[position][depth]=[node.val]
    else:
        ans[position]={depth:[node.val]}
    if node.left:
        Traversal(node.left,position-1,depth+1,ans)
    if node.right:
        Traversal(node.right,position+1,depth+1,ans)
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        ans=dict()
        pos=0
        dep=0
        Traversal(root,pos,dep,ans)
        ret=[]
        for i in sorted(ans.keys()):
            temp=[]
            for j in sorted(ans[i].keys()):
                temp.extend(ans[i][j])
            ret.append(temp)
        #print(ret)
        return ret