1516. 移动 N 叉树的子树 DFS

1516. 移动 N 叉树的子树

给定一棵没有重复值的 N 叉树的根节点 root ，以及其中的两个节点 p 和 q。

移动节点 p 及其子树，使节点 p 成为节点 q 的直接子节点。如果 p 已经是 q 的直接子节点，则请勿改动任何节点。节点 p 必须是节点 q 的子节点列表的最后一项。

返回改动后的树的根节点。

节点 p 和 q 可能是下列三种情况之一：

1. 节点 q 在节点 p 的子树中。
2. 节点 p 在节点 q 的子树中。
3. 节点 p 不在节点 q 的子树中，且节点 q 也不在节点 p 的子树中。

在第 2 种和第 3 种情况中，你只需要移动 p （及其子树），使 p 成为 q 的子节点。但是在第 1 种情况中，树的节点可能会断连，因此你还需要重新连接这些节点。请在解题前仔细阅读示例。

N 叉树的输入序列以层序遍历的形式给出，每组子节点用 null 分隔（见示例）。

例如，上面的树会被序列化为 [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]。

示例 1:

输入: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 4, q = 1
输出: [1,null,2,3,4,null,5,null,6,null,7,8]
解释: 该示例属于第二种情况，节点 p 在节点 q 的子树中。我们可以移动节点 p 及其子树，使 p 成为节点 q 的直接子节点。
注意，节点 4 是节点 1 的最后一个子节点。

示例 2:

输入: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 7, q = 4
输出: [1,null,2,3,null,4,5,null,6,null,7,8]
解释: 节点 7 已经是节点 4 的直接子节点，因此我们不改动任何节点。

示例 3:

输入: root = [1,null,2,3,null,4,5,null,6,null,7,8], p = 3, q = 8
输出: [1,null,2,null,4,5,null,7,8,null,null,null,3,null,6]
解释: 该示例属于第三种情况，节点 p 不在节点 q 的子树中，反之亦然。我们可以移动节点 3 及其子树，使之成为节点 8 的子节点。

提示:

• 节点的总数在 [2, 1000] 间。
• 每个节点都有 唯一 的值。
• p != null
• q != null
• p 和 q 是两个不同的节点（即 p != q ）。

原文链接

做题结果

成功。这题难的地方是最复杂的情况一没有示例。

补充情况一说明：

如果p是q的直接、间接父节点，则把pq从树中断开，q放在原本p的位置，p放在q的最后一个节点（p中原本为q的部分已断开）

方法：DFS

1. 找到 p 和 q 的关系，找到他们的父节点pParent和qParent

2. 如果p是q的父节点，则需要断开q,q从父节点移除，q放在本来p的位置

3. p需要重父节点移除，然后放到q的最后一个子节点

class Solution {
        Node pParent;
        Node qParent;
        public Node moveSubTree(Node root, Node p, Node q) {
            Node pre = new Node(0);
            pre.children = new ArrayList<>();
            pre.children.add(root);
            fillTime(pre,p,q);
            //1.q 是 p 的直接父类
            if(pParent==q) return root;
            //2.p 是 q 的间接、直接父类
 
            int id = pParent.children.indexOf(p);
            pParent.children.remove(p);
            if(isParent(p,q)){
                qParent.children.remove(q);
                pParent.children.add(id,q);
            }
            q.children.add(p);
            return pre.children.get(0);
        }
 
        private boolean isParent(Node p,Node q){
            for(Node item:p.children){
                if(item==q || isParent(item,q)) return true;
            }
            return false;
        }
 
        private void fillTime(Node root,Node p,Node q){
            if(root.children!=null){
                for(Node next:root.children){
                    if(next==p) pParent=root;
                    if(next==q) qParent=root;
                    fillTime(next,p,q);
                }
            }
        }
    }