[LEET CODE] 1038. Binary Search Tree to Greater Sum Tree

# Problem

Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. As a reminder, a binary search tree is a tree that satisfies these constraints: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. Constraints: The number of nodes in the tree is in the range [1, 100]. 0 <= Node.val <= 100 All the values in the tree are unique. root is guaranteed to be a valid binary search tree.

 

# My Answer

class Solution:
    def bstToGst(self, root: TreeNode) -> TreeNode:
        def pl(node,r): # 왼쪽의 모든 노드에 루트값 더해주는 함수
            if node.left:
                node.left.val+=r
                pl(node.left,r)
            if node.right:
                node.right.val+=r
                pl(node.right,r)
                
        if not root:
            return root
            
        if root.right: # 오른쪽 노드 존재하면 
            self.bstToGst(root.right)
            # 가장 깊은 왼쪽 노드가 값이 가장 큼
            rt = root.right
            r = rt.val
            while rt.left:
                r = rt.left.val
                rt = rt.left
            root.val += r

        if root.left:
            self.bstToGst(root.left)
            root.left.val+=root.val
            pl(root.left,root.val) # 왼쪽 노드에는 루트 노드를 다 합해주어야 한다
                    
        return root 

이진 탐색 트리는 오른쪽이 큰 정렬된 트리이므로 오른쪽부터 값을 더해준다.

오른쪽 트리 중에서는 가장 깊은 왼쪽 노드가 가장 값이 크다. 따라서 루트노드에는 오른쪽 트리 중 가장 값이 큰 값을 더해준다

 

왼쪽 트리가 존재하면 우선 왼쪽 트리의 값들을 더해주고,

왼쪽 트리의 모든 노드의 value에 루트 노드의 value값을 더해준다.

 

 

# Solution 1 - 중위 순회로 노드 값 누적

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

클래스 변수 val에 가장 오른쪽 값부터 저장하면서

왼쪽으로 이동시키면서 값을 더해준다.

오른쪽노드 -> 부모 -> 왼쪽 노드 순서대로 값이 더해진다. ( 중위 순회 )