1516. Move Sub-Tree of N-Ary Tree

Given the root of an N-ary tree of unique values, and two nodes of the tree p and q.

You should move the subtree of the node p to become a direct child of node q. If p is already a direct child of q, do not change anything. Node p must be the last child in the children list of node q.

Return the root of the tree after adjusting it.

There are 3 cases for nodes p and q:

1. Node q is in the sub-tree of node p.
2. Node p is in the sub-tree of node q.
3. Neither node p is in the sub-tree of node q nor node q is in the sub-tree of node p.

In cases 2 and 3, you just need to move p (with its sub-tree) to be a child of q, but in case 1 the tree may be disconnected, thus you need to reconnect the tree again. Please read the examples carefully before solving this problem.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

For example, the above tree is serialized as [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14].

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    unordered_map<Node*, Node*> par;
    unordered_map<Node*, int> level;
    void dfs(Node* u, Node* p, int lv) {
        level[u] = lv;
        par[u] = p;
        for(auto& v : u->children)
            dfs(v,u,lv+1);
    }
    bool subOf(Node* u, Node* v) {
        if(level[u] >= level[v]) return false;
        Node* runner = v;
        while(level[runner] > level[u]) runner = par[runner];
        return runner == u;
    }
    void cut(Node* u, Node* v) {
        vector<Node*> newChild;
        for(auto& child : u->children)
            if(child != v)
                newChild.push_back(child);
        u->children = newChild;
    }
public:
    Node* moveSubTree(Node* root, Node* p, Node* q) {
        Node* dummy = new Node(-1, {root});
        dfs(root,dummy,0);
        if(par[p] == q) return root;
        if(subOf(q,p)) {
            cut(par[p],p);
            q->children.push_back(p);
        } else if(subOf(p,q)) {
            cut(par[q],q);
            q->children.push_back(p);
            for(auto& child : par[p]->children)
                if(child == p)
                    child = q;
        } else {
            cut(par[p],p);
            q->children.push_back(p);
        }
        return dummy->children[0]; 
    }
};