최대 이진 트리 구성하기

주어진 고유한 정수 배열을 이용해 최대 이진 트리를 생성하는 문제입니다. 알고리즘은 다음과 같습니다:

• 배열에서 가장 큰 값을 루트 노드로 설정합니다.
• 해당 값의 왼쪽 부분 배열로 좌측 서브트리를 재귀적으로 구성합니다.
• 오른쪽 부분 배열로 우측 서브트리를 재귀적으로 구성합니다.

기본 재귀 구현

class Solution {
public:
    int getMaxIndex(vector<int>& arr) {
        int maxValue = arr[0];
        int position = 0;
        for (int i = 1; i < arr.size(); i++) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
                position = i;
            }
        }
        return position;
    }

    TreeNode* buildMaxTree(vector<int>& data) {
        if (data.empty()) return nullptr;
        
        int idx = getMaxIndex(data);
        TreeNode* node = new TreeNode(data[idx]);
        
        vector<int> leftPart(data.begin(), data.begin() + idx);
        vector<int> rightPart(data.begin() + idx + 1, data.end());
        
        node->left = buildMaxTree(leftPart);
        node->right = buildMaxTree(rightPart);
        
        return node;
    }
};

메모리 최적화 버전

class Solution {
public:
    TreeNode* optimizedBuild(vector<int>& values, int begin, int end) {
        if (begin >= end) return nullptr;
        
        int maxVal = values[begin];
        int maxPos = begin;
        
        for (int i = begin + 1; i < end; i++) {
            if (values[i] > maxVal) {
                maxVal = values[i];
                maxPos = i;
            }
        }
        
        TreeNode* root = new TreeNode(maxVal);
        root->left = optimizedBuild(values, begin, maxPos);
        root->right = optimizedBuild(values, maxPos + 1, end);
        
        return root;
    }
    
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        return optimizedBuild(nums, 0, nums.size());
    }
};

두 이진 트리 병합하기

두 개의 이진 트리를 병합하는 문제로, 노드가 겹치는 경우 값을 더하고, 그렇지 않은 경우 존재하는 노드를 그대로 사용합니다.

재귀 방식

class Solution {
public:
    TreeNode* combineTrees(TreeNode* first, TreeNode* second) {
        if (!first && !second) return nullptr;
        if (first && !second) return first;
        if (!first && second) return second;
        
        first->val += second->val;
        first->left = combineTrees(first->left, second->left);
        first->right = combineTrees(first->right, second->right);
        
        return first;
    }
};

반복 방식 (레벨 순회)

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* tree1, TreeNode* tree2) {
        if (!tree1) return tree2;
        if (!tree2) return tree1;
        
        queue<TreeNode*> nodes;
        nodes.push(tree1);
        nodes.push(tree2);
        
        while (!nodes.empty()) {
            TreeNode* node1 = nodes.front(); nodes.pop();
            TreeNode* node2 = nodes.front(); nodes.pop();
            
            node1->val += node2->val;
            
            if (node1->left && node2->left) {
                nodes.push(node1->left);
                nodes.push(node2->left);
            }
            
            if (node1->right && node2->right) {
                nodes.push(node1->right);
                nodes.push(node2->right);
            }
            
            if (!node1->left && node2->left) {
                node1->left = node2->left;
            }
            
            if (!node1->right && node2->right) {
                node1->right = node2->right;
            }
        }
        
        return tree1;
    }
};

이진 탐색 트리에서 값 찾기

BST의 특성을 활용하여 특정 값을 가진 노드를 검색합니다.

재귀 구현

class Solution {
public:
    TreeNode* findInBST(TreeNode* root, int target) {
        if (!root) return nullptr;
        if (root->val == target) return root;
        
        if (target < root->val) 
            return findInBST(root->left, target);
        else 
            return findInBST(root->right, target);
    }
};

반복 구현

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int value) {
        TreeNode* current = root;
        
        while (current) {
            if (value == current->val) break;
            
            if (value < current->val)
                current = current->left;
            else
                current = current->right;
        }
        
        return current;
    }
};

유효한 이진 탐색 트리 검증

주어진 이진 트리가 BST 조건을 만족하는지 확인합니다.

중위 순회를 통한 검증

class Solution {
private:
    long long previousValue = LONG_MIN;
    
public:
    bool validateBST(TreeNode* node) {
        if (!node) return true;
        
        if (!validateBST(node->left)) return false;
        
        if (node->val <= previousValue) return false;
        previousValue = node->val;
        
        return validateBST(node->right);
    }
};

중위 순회 결과 확인

class Solution {
public:
    void getInorderSequence(TreeNode* root, vector<int>& result) {
        if (!root) return;
        getInorderSequence(root->left, result);
        result.push_back(root->val);
        getInorderSequence(root->right, result);
    }
    
    bool isValidBST(TreeNode* root) {
        vector<int> sequence;
        getInorderSequence(root, sequence);
        
        for (int i = 1; i < sequence.size(); i++) {
            if (sequence[i] <= sequence[i-1]) 
                return false;
        }
        return true;
    }
};