[파이썬 알고리즘 인터뷰][BST] 이진 탐색 트리를 더 큰 수 합게 트리로

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

노드의 값을 현재 노드의 값보다 큰 모든 노드의 값의 합으로 변경

 

책에서 구현된 코드

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

 

기억해야할 기법

• 구현보다 활용이 더 어려울듯
  
  • 문제를 트리로 전환하여 떠올리는 것
  • 문제의 요구사항을 그림으로 떠올리는 것
  • 그 그림이 중위순회를 의미한다는 것을 캐치하는 것

 

내가 구현한 코드

class Solution:
    sum = 0
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root:
            self.bstToGst(root.right)
            root.val = self.sum = self.sum + root.val
            self.bstToGst(root.left)
        return root

• 책에서 구현한 코드와 같다