[Leetcode]1038. Binary Search Tree to Greater Sum Tree

문제 요약

• 알고리즘 분류: Tree, BFS, BST
• 난이도: Medium
• 문제내용:
  • 원래 BST의 모든 키가 자신보다 큰 키들의 합과 원래 키를 더한 값으로 변경되도록 하세요.
• 사이트 주소: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/description/

 

문제풀이

문제의 트리 구조는 아래와 같다.

 

• 노드의 왼쪽 서브트리는 노드의 키보다 작은 키를 가진 노드들로만 이루어져 있어야 합니다.
• 노드의 오른쪽 서브트리는 노드의 키보다 큰 키를 가진 노드들로만 이루어져 있어야 합니다.
• 왼쪽 및 오른쪽 서브트리 또한 이진 탐색 트리여야 합니다.

이번 문제에서는 트리의 탐색하면서 더하는 식으로 진행 하면된다.

트리와 DFS 관한 내용은 아래 글에서 확인 해보면 된다.

• 트리:https://jih3508.tistory.com/87
• DFS: https://jih3508.tistory.com/94

[알고리즘 이론] 깊이 우선 탐색(DFS)

 이번 문제에서는 preOrder, InOrder, PostOrder관한 순서가 아니라 Right → Root → Left 순으로 탐색하면된다.

기존 트리탐색 알면 Right → Root → Left 순으로 탐색하는것 구현은 어렵지 않다. 

구현은 아래코드를 보면 된다.

Python

def treeOrder(node: TreeNode):
    global stackValue
    if(node.right):
        treeOrder(node.right)

    stackValue += node.val
    node.val = stackValue

    if(node.left):
        treeOrder(node.left)

 

Java

public void treeOrder(TreeNode node){

    if(node.right != null){
        treeOrder(node.right);
    }

    stackValue += node.val;
    node.val = stackValue;

    if(node.left != null){
        treeOrder(node.left);
    }

}

Code

Python

class Solution:

    def bstToGst(self, root: TreeNode) -> TreeNode:
        global stackValue
        stackValue = 0
        def treeOrder(node: TreeNode):
            global stackValue
            if(node.right):
                treeOrder(node.right)

            stackValue += node.val
            node.val = stackValue

            if(node.left):
                treeOrder(node.left)

        
        treeOrder(root)
        return root

Java

class Solution {
    int stackValue;
    public TreeNode bstToGst(TreeNode root) {
        
        this.stackValue = 0;
        treeOrder(root);

        return root;
    }

    public void treeOrder(TreeNode node){

        if(node.right != null){
            treeOrder(node.right);
        }

        this.stackValue += node.val;
        node.val = this.stackValue;
        
        if(node.left != null){
             treeOrder(node.left);
        }
        
    }
}