[C++/LeetCode] Trim a Binary Search Tree

Daily LeetCoding Challenge for April, Day 15.

 

문제

주어진 범위 내에 해당하는 원소들로만 이루어지도록 tree를 변경하기

 

아이디어 1: DFS

DFS(Depth First Search)

DFS는 BFS와 비교되는 개념으로, 진행할 수 있는 가장 깊은 node까지 확인하고 상위 노드로 돌아오는 방식이다.

 

문제의 경우는 다음과 같이 두 가지이다.

root의 값이 범위 안에 속할 수 있고, 범위를 벗어날 수 있다.

1. 이때 범위 안에 속한다면 DFS를 활용하여, root->left, root->right 에 대해서도 trim 함수를 재귀적으로 적용해서 잘라진 가지를 가질 수 있도록 하면 된다.

2. 범위를 벗어나는 경우에는 root 자체가 변경되어야 하므로 Binary Tree의 특징에 따라 root node를 교체한다.

binary tree는 이진트리로 root 노드의 값은 자식 노드보다 무조건 값이 크며, 항상 왼쪽 노드보다 오른쪽 노드의 값이 크다. 따라서 경우를 두 가지로 나누어 생각 가능하다.

 

(1) root->val < low 인 경우

이때는 root 노드의 값이 Low보다 작기 때문에 root->left의 노드를 보지 않아도 된다. 왜냐면 이진 트리의 성질에 따라

 

- root 노드의 값이 low보다 작음

- 모든 root->left 노드의 값은 root 노드보다 작음

- root 노드 왼쪽에 있는 모든 노드들은 무조건 low보다 작으므로 확인하지 않아도 됨(범위 벗어남)

 

위와 같은 논리가 적용되기 때문이다. 따라서 root 노드를 root->right 로 교체해주면 된다.

 

(2) root->val > high 인 경우

이 또한 (1)의 경우와 같은 논리로 root 노드를 root->left로 교체해주면 된다.

 

자 그럼 코드를 완성해보자

 

완성

submission: 12ms / 24MB

 

/**
 * 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 {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == NULL)
            return NULL;
        
        else if (root->val >= low && root->val <= high) {
            root->left = trimBST(root->left, low, high);
            root->right = trimBST(root->right, low, high);
            
            return root;
        }
        
        else if (root->val < low)
            return trimBST(root->right, low, high);
        
        else
            return trimBST(root->left, low, high);
    }
};

 

 

아이디어 2: no recursion

재귀를 사용하지 않는다면 어떻게 해야할까?

다음과 같이 while문을 사용하여 left와 right를 직접 탐색해주면 된다.

 

/**
 * 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 {
public:    
   TreeNode* trimBST(TreeNode* root, int low, int high) {
        while (root != NULL && !(root->val >= low && root->val <= high)) {
            if (root->val < low)
                root = root->right;
            else
                root = root->left;
        }
        
        if (root == NULL)
            return NULL;
        
        TreeNode *temp = root;
       
        while (temp->left != NULL) {
            if (temp->left->val < low)
                temp->left = temp->left->right;
            else
                temp = temp->left;
        }
        
        temp = root;
        while (temp->right != NULL) {
            if (temp->right->val > high)
                temp->right = temp->right->left;
            else
                temp = temp->right;
        }
        
        return root;
    }
};