538. Convert BST to Greater Tree

영어 해석이 안되면, 그림 해석을 잘해야되는데, 아직은 그렇지 못한것 같다. 

그래프를 돌면서 값을 더해주면 되는 문제였는데, 왜 어제는 안보였는지 모르겠다. 

 

BST는 자식 - 부모 순으로 순회를 하는 것이다.

이진탐색트리는  전위, 중위, 후위 순회 방법이 있다. 

 

전위 순회(Preorder Traversal): 부모 → 좌 → 우
중위 순회(Inorder Traversal): 좌 → 부모 → 우
후위 순회(Postorder Traversal): 좌 → 우 → 부모

 

문제에서는 우->부모->좌로 순회를 한다. 중위 순회의 변형이라 볼수 있겠다. 

 

오른쪽 자식이 없을때 까지 내려간 다음, val을 우->부모->좌 순서로 더해서 올라오면 된다. 

 

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