'2025/02/23'에 해당되는 글 3건

Leetcode Problem:

• Construct Binary Tree from Preorder and Postorder Traversal

Summary

• Given two integer arrays, preorder and postorder, where preorder is the preorder traversal of a binary tree of distinct values and postorder is the postorder traversal of the same tree, reconstruct and return the binary tree.

Approach

• The approach used is to use a recursive function traversal to construct the binary tree
• The function takes the current node, preorder array index, postorder array index, and the preorder and postorder arrays as parameters
• It creates a new node with the value at the current preorder index, and then recursively constructs the left and right subtrees using the postorder array indices.

Complexity

• O(n) where n is the number of nodes in the tree, since each node is visited once.

Explanation

• The solution uses a recursive function traversal to construct the binary tree
• The function takes the current node, preorder array index, postorder array index, and the preorder and postorder arrays as parameters
• It creates a new node with the value at the current preorder index, and then recursively constructs the left and right subtrees using the postorder array indices
• The base case for the recursion is when the preorder index is greater than or equal to the length of the preorder array, in which case the function returns null
• The function also checks if the current node value matches the current postorder index, and if so, increments the postorder index
• The function then recursively constructs the left and right subtrees, and finally returns the constructed node.

Solution Code:

/**
 * 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* traversal(TreeNode* root, vector& preorder, int& preIdx, vector& postorder, int& posIdx){
        if(preIdx >= preorder.size()) return nullptr;
        root = new TreeNode(preorder[preIdx]);

        if(root->val == postorder[posIdx]){
            posIdx++;
            return root;
        }

        ++preIdx;
        root->left = traversal(root->left, preorder, preIdx, postorder, posIdx);
        if(root->left == nullptr){
            preIdx--;
        }
        if(root->val == postorder[posIdx]){
            posIdx++;
            return root;
        }
        ++preIdx;
        root->right = traversal(root->right, preorder, preIdx, postorder, posIdx);
        if(root->left == nullptr){
            preIdx--;
        }
        if(root->val == postorder[posIdx]){
            posIdx++;
        }
        return root;
    }
    TreeNode* constructFromPrePost(vector& preorder, vector& postorder) {
        int preIdx = 0;
        int posIdx = 0;
        return traversal(nullptr, preorder, preIdx, postorder, posIdx);
    }
};

Leetcode Problem:

• Shortest Distance After Road Addition Queries I

Summary

• Given an integer n and a 2D integer array queries, find the length of the shortest path from city 0 to city n-1 after processing the first i+1 queries.

Approach

• Use a queue to perform BFS from city 0 to city n-1
• For each query, add the new road to the queue and update the distance of each visited city.

Complexity

• O(n*Q) where n is the number of cities and Q is the number of queries

Solution Code:

struct _node{
    int n;
    int cnt;
};
class Solution {
public:
    vector adj[500];
    

    vector shortestDistanceAfterQueries(int n, vector>& queries) {
        vector ans;
        for(int i = 0 ; i < n-1; i++){
            adj[i].push_back(i+1);
        }
        for(int i = 0 ; i < queries.size(); i++){
            queue<_node> que;
            bool visited[500] = {false};
            int a = queries[i][0];
            int b = queries[i][1];
            adj[a].push_back(b);
            
            visited[0] = true;
            for(int j = 0 ; j < adj[0].size(); j++){
                que.push({adj[0][j], 1});
                visited[adj[0][j]] = true;
            }

            while(!que.empty()){
                _node nod = que.front();
                que.pop();
                if(nod.n == n-1){
                    ans.push_back(nod.cnt);
                    break;
                }
                for(int j = 0 ; j < adj[nod.n].size(); j++){
                    int next = adj[nod.n][j];
                    if(visited[next]) continue;
                    visited[next] = true;
                    que.push({next, nod.cnt + 1});
                }
            }
        }
        return ans;
    }
};

Leetcode Problem:

• Find Champion II

Summary

• Find the champion in a directed acyclic graph (DAG) tournament

Approach

• Use depth-first search (DFS) to traverse the graph and identify the champion team
• The champion team is the one that has no stronger team.

Complexity

• O(n + m) where n is the number of teams and m is the number of edges in the graph

Solution Code:

class Solution {
public:
    vector adj[101];
    set leaf;
    bool visited[101];
    set start;
    void dfs(int cur){
        if(visited[cur]) return;
        visited[cur] = true;
        if(adj[cur].size() == 0){
            leaf.insert(cur);
            return;
        }
        for(int i = 0 ; i < adj[cur].size(); i++){
            int next = adj[cur][i];
            dfs(next);
        }
    }
    int findChampion(int n, vector>& edges) {
        if (n == 1) return 0;
        for(int  i = 0 ; i < edges.size(); i++){
            int a = edges[i][0];
            int b = edges[i][1];
            adj[b].push_back(a);
            start.insert(a);
            start.insert(b);
        }
        if(n != start.size()){
            return -1;
        }
        for(auto iter = start.begin(); iter != start.end(); iter++){
            dfs(*iter);
        }
        if(leaf.size() == 1) return *(leaf.begin());
        return -1;
    }
};