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

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Binary Search Tree to Greater Sum Tree - LeetCode>

1. 문제 (이진 탐색 트리(BST)를 터 큰 수 합계 트리로)

BST의 각 노드를 현재값보다 더 큰 값을 가진 모든 노드의 합으로 만들어라.

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
ex : 4 -> 4 + 5 + 6 + 7 + 8 = 30

2. 풀이

재귀탐색을 이용한 풀이

중위 순회로 노드 탐색

• right -> now -> left

3. 코드

# 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
            root.val = self.val
            self.bstToGst(root.left)

        return root

• 결과 :

방식	Status	Runtime	Memory	Language
재귀탐색	[Accepted]	32 ms	14 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋