Burn a Tree

• Time : $O(v + e)$
• Space : $O(v)$

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
int dfs1(TreeNode* node, unordered_map<int,int>& mp) {
    if(!node) return 0;
    int& now = mp[node->val];
    now = max(now, dfs1(node->left, mp));
    now = max(now, dfs1(node->right, mp));
    return now + 1;
}
void dfs2(TreeNode* node, int t, int& res, int o, unordered_map<int,int>& mp) {
    if(!node) return;
    if(node->val == t) res = max(mp[node->val], o);
    if(node->left) {
        dfs2(node->left, t, res, max(o + 1, node->right ? mp[node->right->val] + 1 : 0), mp);
    }
    if(node->right) {
        dfs2(node->right, t, res, max(o + 1, node->left ? mp[node->left->val] + 1 : 0), mp);
    }
}
int Solution::solve(TreeNode* A, int B) {
    int res = 0;
    unordered_map<int, int> mp;
    dfs1(A,mp);
    dfs2(A,B,res,0,mp);
    return res + 1;
}