링크

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/

문제 설명

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.

As a reminder, a binary search tree is a tree that satisfies these constraints:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

제약 조건

The number of nodes in the tree is in the range [1, 100].
0 <= Node.val <= 100
All the values in the tree are unique.

코드

# 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 __init__(self):
        self.array=[]
        self.sum=0
        
    def travel(self,current:TreeNode):
        if current==None:
            return
        else:
            self.travel(current.left)
            self.array.append(current.val)
            self.sum+=current.val
            self.travel(current.right)
    
    def make(self,current:TreeNode,sums_dict:dict):
        if current==None:
            return
        else:
            self.make(current.left,sums_dict)
            current.val=sums_dict[current.val]
            self.make(current.right,sums_dict)
            
    def bstToGst(self, root: TreeNode) -> TreeNode:
        self.travel(root)
    
        previous_sum=self.sum
        sums=0
        sums_dict=dict()
        
        for i in range(len(self.array)):
            if self.array[i] not in sums_dict:
                sums_dict[self.array[i]]=-1
                
            sums_dict[self.array[i]]=previous_sum
            
            sums+=self.array[i]
            
            previous_sum=self.sum-sums
            
        self.make(root,sums_dict)
        return root

해설

1. 중위 순회를 이용하여 이진 "검색" 트리를 정렬된 배열로 만든다.
   위 그림의 예를 들면, 중위 순회의 결과로 [0,1,2,3,4,5,6,7,8]이 나온다.

2. 합의 차이를 구해놓고, 딕셔너리에 담는다. All the values in the tree are unique. 라는 조건이 있으므로 딕셔너리를 사용하면 효율적이다. 왜냐하면 유일한 (키-밸류)쌍의 해시의 조회속도는 O(1)이기 때문이다.

3. 다시 중위 순회를 하되, 이번엔 2.에서 만든 딕셔너리를 이용하여 값을 갱신한다.