1038-kir3i.md

1038. Binary Search Tree to Greater Sum Tree

Solution

• 시간복잡도: O(N)

• 알고리즘

  트리 순회, 이진 탐색 트리

• 풀이설명

  1. val이 큰 노드부터 조회해야하므로 BST의 특성을 이용해 가장 오른쪽 노드부터 방문합니다.
  2. 오른쪽 노드 - 가운데 노드 - 왼쪽 노드 순으로 방문하는 중위순회를 하면 val이 큰 순서로 노드를 방문할 수 있습니다. 순회를 하면서 sum에 각 노드의 val 값을 누적하고, 순회 순서가 온 노드에 대해 val에 sum을 더한 값을 할당합니다.
  3. 순회를 모두 마치면 문제에서 요구하는 Greater Sum Tree가 됩니다.

• 소스코드

# 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 bstToGst(self, root):
        self.updateVal(root, 0)
        return root

    def updateVal(self, node, sum):
        if not node:
            return 0

        if node.right:
            sum = self.updateVal(node.right, sum)

        sum += node.val
        node.val = sum

        if node.left:
            sum = self.updateVal(node.left, sum)

        return sum