greentea31's Note

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

풀이 과정

이진 탐색 트리를 Greater Sum Tree로 바꿔야 한다. Greater Sum Tree의 각 노드 값은, 기존 이진 탐색 트리에서 자신보다 큰 값을 가진 노드 값들의 합이다.

문제의 예시를 보면 파란색 글씨로 써져있는 Greater Sum Tree의 각 노드 값이, 기존 이진 탐색 트리의 각 노드에서 자신보다 더 큰 값을 가진 노드 값들의 합을 값으로 가지고 있음을 확인할 수 있다.

트리의 순회 3가지를 떠올려보자.

1. 전위 순회

루트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리

2. 중위 순회

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트

3. 후위 순회

왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트

이 문제는 중위 순회 과정을 살짝 바꾸어 오른쪽 서브 트리 -> 루트 -> 왼쪽 서브 트리 순으로 순회하게끔 하고 값을 누적해나가면 해결할 수 있다.

소스 코드

class Solution:
    val = 0
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root:
            self.bstToGst(root.right)
            self.val += root.val
            root.val = self.val
            self.bstToGst(root.left)
        return root