Day 43 | Graph and Tree Practice [Leetcode] II | C++

Find Eventual Safe States

Solution

Everything other than cycle will end at a terminal state. So will store reachTerminal[i] = true, if all children can reach terminal points

Solution Implementation

class Solution {
public:
    void dfs(int u, vector<vector<int>>& g, vector<int>& vis, vector<int>& reachTerminal){
        vis[u] = 1;
        reachTerminal[u] = 1;
        for(int i : g[u]){
            if(vis[i] == 1){
                reachTerminal[u] = 0;
                continue;
            }
            if(vis[i] == 0)dfs(i,g,vis,reachTerminal);
            reachTerminal[u] &= reachTerminal[i];
        }
        vis[u] = 2;
    }
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        vector<int> reachTerminal(n);
        vector<int> vis(n);
        for(int i = 0; i < n; i++){
            reachTerminal[i] = (graph[i].size() == 0);
        }
        vector<int> ans;
        for(int i = 0; i < n; i++){
            if(vis[i] == 0)
                dfs(i,graph,vis,reachTerminal);
        }
        for(int i = 0; i < n; i++){
            if(reachTerminal[i])
                ans.push_back(i);
        }
        return ans;
    }
};

Add One Row to Tree

Solution

It is just implementation, we just have to add row. Not much logic here

Solution Implementation

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if(!root)return nullptr;
        if(d == 1){
            TreeNode* ans = new TreeNode(v);
            ans->left = root;
            return ans;
        }
        if(d == 2){
            {
                auto temp = root->left;
                root->left = new TreeNode(v);
                root->left->left = temp;
            }
            {
                auto temp = root->right;
                root->right = new TreeNode(v);
                root->right->right = temp;
            }
            return root;
        }
        addOneRow(root->left,v,d-1);
        addOneRow(root->right,v,d-1);
        return root;
    }
};

Maximum Width of Binary Tree

Solution

For each level store the max shifting to left and to right. In end, find the level with max difference.

Solution Implementation

/**
 * 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 {
    map<unsigned long long,pair<unsigned long long,unsigned long long>> lev;
    
public:
    int widthOfBinaryTree(TreeNode* root) {
        dfs(root);
        unsigned long long ans = 0;
        for(auto i: lev)ans = max(ans,i.second.first-i.second.second+1);
        return (int)ans;
    }
    void dfs(TreeNode* root, unsigned long long h = 0, unsigned long long shift = 1){
        if(!root)return;
        if(lev.count(h)){
            lev[h].first = max(lev[h].first,shift);
            lev[h].second = min(lev[h].second,shift);
        }else{
            lev[h] = make_pair(shift,shift);
        }
        dfs(root->left,h+1,shift*2);
        dfs(root->right,h+1,shift*2+1);
    }
};

All Nodes Distance K in Binary Tree

Solution

You can solve this problem with a simple DFS. But there is one problem, nodes are directed from top to bottom from root. There is no backward edge i.e. child to parent so running DFS from any node is difficult. What you can do is run 1 DFS to mark all parents, this give you the missing edge and now you can run DFS from any source.

Solution Implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
map<TreeNode*,TreeNode*> parent;
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
        vector<int> ans;
        setParent(root);
        dfs(target,nullptr,K,ans);
        return ans;
    }
    void setParent(TreeNode* root, TreeNode* p = nullptr){
        if(!root)return;
        parent[root] = p;
        setParent(root->left,root);
        setParent(root->right,root);
    }
    void dfs(TreeNode* root, TreeNode* p, int distance, vector<int> &ans){
        if(!root)return ;
        if(distance == 0)ans.emplace_back(root->val);
        if(root->left != p)dfs(root->left,root,distance-1,ans);
        if(root->right != p)dfs(root->right,root,distance-1,ans);
        if(parent[root] != p)dfs(parent[root],root,distance-1,ans);
    }
};

Please like and share my posts if they are helpful.