리트코드 1038번 Binary Search Tree to Greater Sum Tree (python)

Problem

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

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:
    def dfs(self, node, greater_sum=0):
        if node is None:
            return 0

        if node.right is not None:
            greater_sum = self.dfs(node.right, greater_sum)

        node.val += greater_sum

        if node.left is not None:
            return self.dfs(node.left, node.val)

        return node.val

    def bstToGst(self, root: TreeNode) -> TreeNode:
        self.dfs(root)
        return root

DFS를 통해 오른쪽 → 중간 → 왼쪽 순으로 탐색하였다.

다른 풀이

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

책에 나온 조금더 간결한 풀이이다. 합을 변수로 넘기지 않고 클래스의 멤버 변수로 선언하였다.

Reference

파이썬 알고리즘 인터뷰 51번