LeetCode 1490. 克隆 N 叉树（DFSBFS）

文章目录

1. 题目2. 解题2.1 DFS2.2 BFS

1. 题目

给定一棵 N 叉树的根节点 root ，返回该树的深拷贝（克隆）。

N 叉树的每个节点都包含一个值（ int ）和子节点的列表（ List[Node] ）。

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

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

进阶：你的答案可以适用于克隆图问题吗？

示例 1： 输入：root = [1,null,3,2,4,null,5,6] 输出：[1,null,3,2,4,null,5,6] 示例 2： 输入：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] 输出：[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] 提示： 给定的 N 叉树的深度小于或等于 1000。 节点的总个数在 [0, 10^4] 之间

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/clone-n-ary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 DFS

/* // 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 {//C++ public: Node* cloneTree(Node* root) { if(!root) return root; Node* r = new Node(root->val) for(auto it : root->children) { Node* child = cloneTree(it); r->children.push_back(child); } return r; } };

124 ms 175 MB

""" # Definition for a Node. class Node: def __init__(self, val=None, children=None): self.val = val self.children = children if children is not None else [] """ class Solution: # py3 def cloneTree(self, root: 'Node') -> 'Node': if not root: return root r = Node(root.val) for c in root.children: child = self.cloneTree(c) r.children.append(child) return r

84 ms 17.5 MB

2.2 BFS

使用2个队列，同步进行出入队即可 class Solution { public: Node* cloneTree(Node* root) { if(!root) return root; Node* r = new Node(root->val); queue<Node*> q, qc; q.push(root); qc.push(r); Node* cur, *cur_, *c; while(!q.empty()) { cur = q.front(); cur_ = qc.front(); q.pop(); qc.pop(); for(auto it : cur->children) { if(!it) { cur_->children.push_back(NULL); continue; } q.push(it); c = new Node(it->val); cur_->children.push_back(c); qc.push(c); } } return r; } };

116 ms 175.1 MB

---

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！