51. Binary Search Tree to Greater Sum Tree

리트코드

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

1. 중위 순회로 노드 값 누적

# 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: 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
        

• 자신보다 같거나 큰 값을 구하려면 자기 자신을 포함한 우측 자식 노드의 합을 구하면 된다.

  • BST의 우측 자식 노드는 항상 부모노드보다 큰 값이기 때문이다.

<더 큰 수 합계 트리를 위한 탐색 순서>

• root를 입력받았을 때 먼저 맨 오른쪽까지 내려가고, 그다음 부모 노드, 다시 왼쪽 노드 순으로 이동하면서 자신의 값을 포함해 누적한다. 오른쪽-부모-왼쪽 순으로 이어지며, 오른쪽 자식부터 운행하는 중위 순회(In-Order)에 해당됨을 알 수 있다.

• self.val은 지금까지 누적된 값이고, root.val은 현재 노드의 값이다.

  • 즉, 중위 순회를 하면서 현재 노드의 값을 자기 자신을 포함한 지금까지의 누적된 값과 합한다.

• 최초 self.val은 클래스 멤버 변수로 선언하고 0이 되도록 직관적으로 선언했다.

• root가 있을 때만 처리되게 했으며, root.val을 조작한 이후에는 다시 root를 리턴한다.

  • root를 리턴하지 않아도 관계 없다. 재귀 호출 시 리턴 값은 사용하지 않기 때문이다.

  • 파이썬은 모든 변수가 참조이기 때문에, 객체 내부의 값을 변경하면 해당 객체를 가리키는 모든 변수는 자연스럽게 따라서 값이 변한다.

  • 리트코드는 아마 호출 시 root = solution.bstToGst(root)와 같은 형태로 리턴 값을 받아오도록 구현되어 있을 것이다.

    • 이때 리턴 값을 돌려주지 않으면 root는 None이 되어 버린다.

    • 리트코드에서 리턴 값을 주지 않으면 정답이 출력되지 않는 것도 그 때문일 것이다.
      따라서 반드시 return root를 명시한다.