1038. Binary Search Tree to Greater Sum Tree

Binary Search Tree to Greater Sum Tree - LeetCode

이진 탐색 트리가 주어진다.

주어진 이진 탐색 트리 노드들의 값을 (기존 값 + 자신보다 큰 값을 가진 노드들의 값의 합)으로 변환한 뒤 root를 반환하는 문제다.

 

새로운 트리를 만드는 것이 아니라 기존 트리를 조작해서 문제 조건대로 만든 뒤 입력받은 root를 그대로 반환해야 한다.

 

1. Recursion 01

 

class Solution(object):
    def bstToGst(self, root):
        def dfs(cur, val, saved):
            if not cur.left and not cur.right:
                cur.val += saved
                return cur.val

            right = 0
            if cur.right:
                right = dfs(cur.right, val, saved)
            cur.val += right
            if not right:
                cur.val += saved
            if not saved:
                saved = cur.val
            else:
                saved = max(saved, cur.val)
            left = 0
            if cur.left:
                left = dfs(cur.left, cur.val, saved)
            return max(cur.val, left)

        dfs(root, 0, 0)
        return root

이진 탐색 트리는 자신보다 오른쪽에 있는 값은 모두 크고, 왼쪽에 있는 값은 작다는 성질을 가지고 있다.

우선 오른쪽부터 탐색을 시작, 오른쪽 서브 트리의 리프 노드에서 거슬러 올라오면서 saved 값을 업데이트해주고, 왼쪽에선 saved 값을 반영해주는 방식으로 접근했다.

 

우선 반례가 있어서 통과할 수 있었고, 주어진 예제만으로는 통과하는 코드를 작성하지 못했다.

첫 통과할 때까지 1시간 넘게 걸린 것 같다.

 

2. Recursion 02

class Solution(object):
    def bstToGst(self, root):
        def dfs(cur, val, saved):
            if not cur.left and not cur.right:
                cur.val += saved
                return cur.val

            right = 0
            if cur.right:
                right = dfs(cur.right, val, saved)

            cur.val += right if right else saved
            saved = cur.val

            left = 0
            if cur.left:
                left = dfs(cur.left, cur.val, saved)

            return left if left else cur.val

        dfs(root, 0, 0)
        return root

1번 로직과 동일하지만 코드를 정리하고 나름대로 이해하기 쉽게 리팩터링 했다.

포인트는 cur.val과 saved를 업데이트하는 곳인데 cur.val의 값은 오른쪽 서브 트리가 존재하면 오른쪽 재귀 탐색의 결과를 더해주고, 존재하지 않는다면 기존에 saved값을 더해준다.

 

이후 왼쪽도 탐색을 하고, 마지막에 반환할 땐 왼쪽 서브 트리가 존재하면 왼쪽 서브 트리의 노드 값을, 존재하지 않는다면 현재 노드 값을 반환했다.

 

3. Reverse - Inorder Traversal

class Solution(object):
    saved = 0

    def bstToGst(self, root):
        def dfs(cur):
            if cur.right:
                dfs(cur.right)
            cur.val += self.saved
            self.saved = cur.val
            if cur.left:
                dfs(cur.left)

        dfs(root)
        return root

사실 이 문제는 그냥 역방향으로 Inorder 순회를 하면 해결된다.

그럼 단순히 역방향으로 순회를 하면서 현재 노드보다 큰 값을 어떻게 가지고 이동하냐는 그냥 함수 바깥쪽에 전역 변수 하나 사용해서 해결하면 된다.

 

첫 번째 풀이가 굉장히 오래 걸렸던 게 한 번의 순회를 하면서 누적해서 더해주어야 하는 값을 재귀 함수 내에서 계속 가지고 있는 상태에서 왼쪽, 오른쪽 조건을 다르게 줘야 했기 때문이었다.

 

그리고 나는 누적되는 값이 재귀 함수마다 업데이트해줘야 하기 때문에 값을 함수에 넣어서 사용했고 재귀 호출도 값을 반환하는 방식으로 디자인을 했는데, 나는 값을 반환하는 식의 재귀 호출은 그냥 재귀를 도는 것보다 디자인을 굉장히 못한다.

 

결국 내가 작성한 코드나 3번 코드나 결은 다를 게 없는데 이진 탐색 트리와 재귀를 사용하는 이해도 차이에서 갈렸다. 관리해야 하는 값을 재귀 함수를 통해서 무조건 가지고 움직여야 한다고 무의식적으로 생각하고 코드를 작성한 게 패착 같다.