[LeetCode] 1038. Binary Search Tree to Greater Sum Tree (Python)

• Reference

Solution

# 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:
    val = 0

    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root:
            self.bstToGst(root.right)

            # self.val: 지금까지 누적된 값
            # root.val: 현재 노드의 값
            # 즉, inorder 방식으로 현재 노드의 값을 자기 자신을 포함한 지금까지의 누적된 값과 합침

            # self.val에 현재 노드의 값 root.val을 더함 -> 현재 노드의 값을 이전에 방문한 노드들의 합과 더하는 것을 의미
            # root.val을 self.val로 업데이트하여 현재 노드의 값을 누적된 값으로 변경
            self.val += root.val
            root.val = self.val

            self.bstToGst(root.left)

        return root