3.9  如何复制二叉树

3.9 如何复制二叉树

【出自GG面试题】

难度系数：★★★☆☆ 被考察系数：★★★★☆

题目描述：

给定一个二叉树根结点，复制该树，返回新建树的根结点。

分析与解答：

用给定的二叉树的根结点root来构造新的二叉树的方法：首先创建新的结点dupTree，然后根据root结点来构造dupTree结点（dupTree.data=root.data），最后分别用root的左右子树来构造dupTree的左右子树。根据这个思路可以实现二叉树的复制，使用递归方式实现的代码如下：

程序的运行结果如下：

原始二叉树中序遍历：-1 3 9 6 -7

新的二叉树中序遍历：-1 3 9 6 -7

算法性能分析：

这种方法对给定的二叉树进行了一次遍历，因此，时间复杂度为O（N），此外，这种方法需要申请N个额外的存储空间来存储新的二叉树。