Leetcode - 1038. Binary Search Tree to Greater Sum Tree

문제

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

풀이

일반적인 트리 순회구조와 다르게 무조건 우측 노드(BST에서 값이 큰 노드)부터 순회해야 하는 구조다.

일부 노드 값이 제대로 안 나와서 결국 힌트를 봤는데 내가 생각한 거랑 큰 차이가 없어서 너무 아쉬웠던 문제.

class Solution:
    cur_sum = 0

    def bstToGst(self, root: TreeNode) -> TreeNode:
        if not root:
            return 0

        self.bstToGst(root.right)
        self.cur_sum += root.val
        root.val = self.cur_sum
        self.bstToGst(root.left)

        return root