Lintcode375 Clone Binary Tree so
【题目描述】
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'
| ^
|----------------------------|
最后，拆分链表，就可以得到深拷贝的链表了。
【参考答案】
