[알고리즘] 이진 탐색 트리(BST)를 더 큰 수 합계 트리로

이진 탐색 트리(BST)를 더 큰 수 합계 트리로

자신보다 같거나 큰 값을 구하려면 BST에서는 자신을 포함한 우측 자식 노드의 합을 구하면 된다. 이는 중위 순회를 돌며 누적 값을 넣어주면 된다.

책 풀이

class Solution:
    val: int = 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