[C++/LeetCode] Convert BST to Greater Tree

Daily LeetCoding Challenge for April, Day 16.

 

문제

다음과 같이 Binary Search Tree가 주어졌을 때 이를 반대로 만드는 것이다.

 

아이디어: DFS

어제에 이어서 오늘도 DFS를 사용한다.

로직을 짜기 전에 문제에서 값이 수정되는 원리를 파악해보자.

root의 값은 어떻게 수정될까?

바로 [root->right의 수정으로 얻어진 값 중 가장 큰 값 + root->val] 의 결과이다.

따라서 가장 먼저 할일은 바로 root->right를 수정하는 것이다.

그 후 root->node의 값을 수정해준다.

root->left의 값은 root node의 value를 더한 후에, root->left에 대해서 같은 로직을 반복하는 것이다.

 

그럼 root->right를 수정하고 얻어진 값은 어떻게 구할 수 있을까?

이때 private으로 선언된 멤버 변수, 즉 재귀와 상관없는 외부 변수가 하나 있어야 한다.

이 외부 변수에다 상위 node의 값에 하위 right node의 값을 더해서 저장하고, 이 변수의 값으로 상위 node의 값을 변경하면 수정이 완료된다.

이는 node->left에 대해서도 마찬가지이다.

 

예외 사항

node가 NULL일 경우에 DFS를 종료할 수 있도록 return root를 해준다.

 

완성

submission: 40ms / 33.5MB

 

class Solution {
private:
    int offset = 0;
public:
    TreeNode* convertBST(TreeNode* root) {
        if (!root)
            return root;
        
        convertBST(root->right);
        root->val += offset;
        offset = root->val;
        convertBST(root->left);

        return root;
    }
};

 

offset 변수를 0으로 초기화하여 쓰레기값이 들어가지 않도록 해준다.

재귀를 돌면서 offset값이 변경되고, 이 값을 더한 값으로 node가 수정되면서 tree가 변경된다.

root->left에 대해서도 같은 로직을 적용할 수 있다. 이때에도 offset 값은 여전히 저장되어 있으므로 추가 로직은 필요하지 않다.