51. Binary Search Tree to Greater Sum Tree

🎯 leetcode - 1038. Binary Search Tree to Greater Sum Tree

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 51번 문제

📌 날짜

2020.02.21

📌 시도 횟수

1 try

💡 Code

class Solution:
    value = 0

    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root.right:
            self.bstToGst(root.right)
            
        self.value += root.val
        root.val = self.value

        if root.left:
            self.bstToGst(root.left)

        return root

+ 쪼-금 다른 책에 나온 코드 😉

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

💡 문제 해결 방법

- 중위 순회(Inorder Traversal) 방법을 이용했다.
- 중위 순회(오른쪽→노드→왼쪽)로 노드에 접근하면서 현재 노드의 val을 value라는
클래스 변수에 누적했다.
- 값을 계속 누적시켜 변경하기 위해 클래스 변수 value를 사용했다.

💡 새롭게 알게 된 점

- 중위 순회에 대해 까먹고 있었는데 다시 복습할 수 있는 기회가 되었다.

🎈 중위 순회 순회 방법

1. 현재 노드의 왼쪽(오른쪽) 서브트리를 순회한다.
2. 현재 노드를 방문한다.
3. 현재 노드의 오른쪽(왼쪽) 서브트리를 순회한다.

• ⭐참고 블로그⭐

---