[leetcode] 538. Convert BST to Greater Tree / 1038. Binary Search Tree to Greater Sum Tree 파이썬 코드

https://leetcode.com/problems/convert-bst-to-greater-tree/

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

 

이진 탐색 트리 (binary search tree, BST)가 있을 때

그 노드의 값과 그 노드보다 큰 값을 모두 더한 값으로 노드를 다시 채워 넣는 문제이다.

 

DFS를 하면 된다는 건 감이 왔지만, 코드를 짜지 못했다는 게 문제다.

 

전위 순회 (preorder), 중위 순회 (inorder), 후위 순회 (post order)의 순서는 각각 VLR, LVR, LRV 이다.

(V는 부모, L은 왼쪽 자식, R은 오른쪽 자식)

 

이 문제는 inorder traversal을 reverse 하면 된다는 걸 알 수 있다.

 

class Solution:
    def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        currSum = 0
        def dfs(node):
            if not node:
                return

            nonlocal currSum
            dfs(node.right)
            temp = node.val
            node.val += currSum
            currSum += temp
            dfs(node.left)
        
        dfs(root)
        return root

 

함수 밖에서 정의한 변수를 함수 안에서 사용하기 위해서는 nonlocal 이라는 키워드를 사용하면 된다는 것을 알게 되었다.