1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public Node cloneTree(Node root) {
        if (root == null) {
            return null;
        }
        Node newRoot = new Node(root.val, new ArrayList<>());
        dfs(root, newRoot);
        return newRoot;
    }

    private void dfs(Node ptr, Node newPtr) {
        for (Node child : ptr.children) {
            Node newChild = new Node(child.val, new ArrayList<>());
            newPtr.children.add(newChild);
            dfs(child, newChild);
        }
    }
}

DFS就完事了. 只不过是在parent的位置去添加children.
时间复杂度: O(n)
空间复杂度: O(n)
n是nodes的个数.

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public Node cloneTree(Node root) {
        if (root == null)
            return null;
        Node newRoot = new Node(root.val, new ArrayList<>());
        for (Node child : root.children) {
            newRoot.children.add(cloneTree(child));
        }
        return newRoot;
    }
}

这个写法更好. 递归函数的功能就是给一个tree, 返回给我们一个复制好的. 于是我们就可以把children都复制好然后添加到当前node
的copy的list中去即可.

时间复杂度和空间复杂度不变.