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

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

leetcode - Binary Search Tree to Greater Sum Tree

문제 유형 : 이진트리, 이진탐색트리, dfs

문제 난이도 : Medium

 

문제

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 the 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)의 루트가 주어진다. Greater Sum Tree로 변환하시오.

각 요소가 기존 BST에서 자신보다 큰 요소들 + 자신을 합해야 합니다.

 

풀이

inorder_traversal을 역방향으로 하여 해결할 수 있다.

오른쪽 노드가 가장 크므로, 오른쪽 노드부터 순회해주면 된다.

누적합에 대한 참조 때문에, 왼쪽 노드를 탐색할 때, sum에는 오른쪽의 합이 담겨있다.

 

 

코드

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    void traverse(TreeNode* root, int &sum) {
        if(root == NULL) return;
        traverse(root -> right, sum);
    
        sum += root -> val;
        root -> val = sum;

        traverse(root -> left, sum);
    }
    TreeNode* bstToGst(TreeNode* root) {
        int sum = 0;
        traverse(root, sum);
        return root;
    }
};