1038. Binary Search Tree to Greater Sum Tree

요새 왤케 이진 트리 문제가 재밌는지 모르겠네요?

 

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

Binary Search Tree to Greater Sum Tree - LeetCode

---

이번 문제는 제일 오~~~른쪽으로 갔다가 왼쪽 갔다가 다시 올라오면서 수를 갱신하는 문제입니다.

 

이런 식

되게 쉬워요.

 

단, 언제 어느 순간에 갱신을 해주냐가 중요한거 같습니다.

 

이 문제는 아마 중위 순회 일거 같네요.

 

중위 순회

But 위 그림과는 다르게 왼쪽으로 가는게 아닌 오른쪽을 먼저 둘러봐야하는 것이 문제의 핵심입니다.

 

코드 갑니다.

 

# 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 __init__(self):
        self.val = 0
        self.result = []
    
    def updateBst(self, root: TreeNode) -> TreeNode:
        if root == None:
            return 0
        self.bstToGst(root.right)
        self.val += root.val
        root.val = self.val
        self.bstToGst(root.left)
    
    
    def bstToGst(self, root: TreeNode) -> TreeNode:
        self.updateBst(root)
        
        return root

 

굿 !

---

이상 1038. Binary Search Tree to Greater Sum Tree였습니다. ^_^