X

LEETCODE 1490. Clone N-ary Tree 解题思路分析

题目大意:

Given a root of an N-ary tree, return a deep copy (clone) of the tree.

Each node in the n-ary tree contains a val (int) and a list (List[Node]) of its children.

class Node {
    public int val;
    public List<Node> children;
}

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

Follow up: Can your solution work for the graph problem?

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: [1,null,3,2,4,null,5,6]

Example 2:

Input: root = [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]
Output: [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]

Constraints:

  • The depth of the n-ary tree is less than or equal to 1000.
  • The total number of nodes is between [0, 10^4].

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1490

解题思路分析:

这道题考查的是深度拷贝,在java语言中,使用等号赋值实际上只是地址(指针)拷贝,并不能实现深度拷贝的效果。因此对于每个节点对象我们都必须重新new一个新的对象,然后将原节点的每个参数赋值到新的节点中。

解题时,我们使用dfs递归方式遍历树中每一个节点,首先new一个新的节点对象用于拷贝当前节点,将新的节点值设置为原节点值。另外新建一个子节点列表,递归当前节点的每一个子节点,递归返回值(拷贝后的子节点)加入到新建的子节点列表中。最后将该列表赋值到新建节点的列表对象。当前递归的返回值为该新建节点。

实现代码:

public Node cloneTree(Node root) {
    if(root==null) return null; // 如果节点为空,返回空
    Node node = new Node(); // 新建一个节点对象
    node.val=root.val; // 设置新的节点值为元节点值
    List<Node> children=new ArrayList<>(); // 新建子节点列表
    for(Node c : root.children){ // 循环每一个子节点
        // 递归拷贝每一个子节点,并将其加入新建子节点列表
        children.add(cloneTree(c));
    }
    // 设置拷贝后的子节点列表
    node.children = children;
    // 返回当前新建的节点对象
    return node;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 100.00% of Java online submissions for Clone N-ary Tree.

Memory Usage: 41.2 MB, less than 100.00% of Java online submissions for Clone N-ary Tree.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1490-clone-n-ary-tree-解题思路分析/
Categories: leetcode
kwantong: