【题目描述】

 For the given binary tree, return a deep copy of it.

深度复制一个二叉树,给定一个二叉树，返回一个他的克隆品。

【题目链接】

www.lintcode.com/en/problem/clone-binary-tree/

【题目解析】

假设有如下链表：

|—————|

|                 v

1  –> 2 –> 3 –> 4

节点1的random指向了3。首先我们可以通过next遍历链表，依次拷贝节点，并将其添加到原节点后面，如下：

|—————————–|

|                                   v

1  –> 1′ –> 2 –> 2′ –> 3 –> 3′ –> 4 –> 4′

          |                          ^

          |———————-|

因为我们只是简单的复制了random指针，所以新的节点的random指向的仍然是老的节点，譬如上面的1和1’都是指向的3。

调整新的节点的random指针，对于上面例子来说，我们需要将1’的random指向3’，其实也就是原先random指针的next节点。

|——————————|

|                                   v

1  –> 1′ –> 2 –> 2′ –> 3 –> 3′ –> 4 –> 4′

          |                                  ^

          |—————————-|

最后，拆分链表，就可以得到深拷贝的链表了。

【参考答案】

www.jiuzhang.com/solutions/clone-binary-tree/

posted on 2018-04-13 23:14 bokeyyy 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为ccccnnnblog原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/ccccnnnblog/p/8824696.html