[Leetcode][Java] 1038 Binary Search Tree to Greater Sum Tree ( BST를 GreaterSumTree로 변환 )

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.

BST의 root 노드가 주어지고, 이 노드를 Greater Tree로 변환하여라.

BST의 모든 key값은 -> 초기값 + 해당 노드보다 큰 key값을 가진 노드의 합으로 변경된다. 

아래는 BST가 만족하는 제약사항들이다.

• 왼쪽 하위 트리는 해당 노드의 key값보다 작은 노드들로만 구성된다.
• 오른쪽 하위 트리는 해당 노드의 key값보다 큰 노드들로만 구성된다.
• 오른쪽, 왼쪽의 모든 하위 트리는 BST이다. 

---

DFS를 이용해서 해당 문제의 답을 구해보자.

자기 자신보다 큰 값을 가지고 있는 노드들의 합을 구해야 하므로 가장 큰 값을 가지고 있는 노드부터 자기 자신의 값을 더해가면서 그 합들을 구해가면 된다. 

BST의 특성상 가장 큰 값은 트리의 오른쪽 노드들만 타고 가면 나오고

가장 끝의 도달한 순간 부터는 해당 노드의 value를 total sum과 더해가면서 노드의 value값을 변환하면 된다. 

    private void dfs(TreeNode node) {
        if (node.right != null) {
            dfs (node.right);
        }
        int temp = node.val;
        node.val = sum + temp;
        sum = node.val;

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

오른쪽 subTree를 모두 순회한 후에 왼쪽 서브 트리를 같은 방식으로 순회하면 된다.

(왼쪽의 subTree의 경우에도 가장 큰 값은 오른쪽 끝에 존재) 

 

이제 해당 메서드를 호출하는 메서드를 보자.

누적 sum을 나타내는 값은 전역변수로 선언하였다.

    int sum = 0;
    public TreeNode bstToGst1(TreeNode root) {
        
        if (root != null) {
            dfs(root);
        }

        return root;
    }

 

문제 출처

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

Binary Search Tree to Greater Sum Tree - LeetCode