[leetcode] Convert BST to Greater Tree

유의할점

right가 먼저인 중위 순회

어려운 문제 아님. 큰 수는 오른쪽 서브트리에 있으니 오른쪽 서브트리를 순회해서 얻은 누적합을 루트에 더하면 된다는 생각으로 풀었다.

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.

bold처리된 문장해석에 있어서 어려움이 있었다.

풀이

오른쪽서브트리→루트→왼쪽서브트리 순회이다.

순회하면서 루트에 있는 값을 누적한다. 누적합과 루트의 값을 더한값으로 누적합과 루트의 값을 갱신한다.

ex1 )

8 → 7 → 6 → 5 → 4 → 3 → 2 → 1 → 0 순으로 방문. 따라서 누적합은 다음과 같이 갱신된다.

8 → 15 → 21 → 26 → 30 → 33 → 35 → 36 → 36

코드

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) {}
 * };
 */
class Solution {
private: int acc = 0;
public:
    void Traversal(TreeNode* root) {
        if(root == NULL)
            return;
        
        Traversal(root->right);
        root->val += acc;
        acc = root->val;
        Traversal(root->left);
    }
    
    
    TreeNode* convertBST(TreeNode* root) {
        Traversal(root);
        return root;
    }
};