python实现复制二叉树

广告位

python实现复制二叉树 google笔试题 题目描述: 给定一个二叉树根结点,复制该树,返回新建树的根结点…

python实现复制二叉树

google笔试题
题目描述:
给定一个二叉树根结点,复制该树,返回新建树的根结点 。
分析与解答:
用给定的二叉树的根结点 root来构造新的二叉树的方法为:首先创建新的结点 dupTree,
然后根据 root 结点来构造 dupTree 结点( dupTree.data=root.data), 最后分别用 root 的左右子 树来构造 dupTree 的左右子树。 根据这个思路可以实现二叉树的复制,使用递归方式实现的 代码如下:

class BiTNode:     def __init__(self):         self.data=None         self.lchild=None         self.rchild=None def creatDupTree(root):     if root==None:         return None     dupTree=BiTNode()     dupTree.data=root.data     dupTree.lchild=creatDupTree(root.lchild)     dupTree.rchild=creatDupTree(root.rchild)     return dupTree def printreemidorder(root):     if root==None:         return     if root.lchild!=None:         printreemidorder(root.lchild)     print(root.data)     if root.rchild!=None:         printreemidorder(root.rchild) def constructTree():     root=BiTNode()     node1=BiTNode()     node2=BiTNode()     node3=BiTNode()     node4=BiTNode()     root.data=6     node1.data=3     node2.data=-7     node3.data=-1     node4.data=9     root.lchild=node1     root.rchild=node2     node1.lchild=node3     node1.rchild=node4     node2.lchild=node2.rchild=node3.lchild=node3.rchild=     node4.lchild=node4.rchild=None     return root if __name__=='__main__':     root1=constructTree()     root2=creatDupTree(root1)     print('原始二叉树中序遍历')     printreemidorder(root1)     print('n')     print('新的二叉树中序遍历')     printreemidorder(root2) 
原始二叉树中序遍历 -1 3 9 6 -7   新的二叉树中序遍历 -1 3 9 6 -7  

剪烛西窗, 程

关于作者: 剪烛西窗

为您推荐