Chap02_귀속과 분치_두 그루의 두 갈래 나무가 동일한지 아닌지를 판단하다

#  ： ， 。

#  ： 。

#  ：（ ）

# 1.   

# 2.  

# 3.  

 1 # encoding:utf-8

 2 
 3 class Node:
 4     def __init__(self, data):
 5         self.data = data
 6         self.left = None
 7         self.right = None
 8 
 9 # ---------------------------------------
10 #  
11 #----------------------------------------
12 n1 = Node(1)
13 n2 = Node(2)
14 n3 = Node(3)
15 n4 = Node(4)
16 n5 = Node(5)
17 
18 n1.left  = n2
19 n1.right = n3
20 n2.left  = n4
21 n2.right = n5
22 
23 root1 = n1
24 root2 = n1
25 
26 #----------------------------------------
27 # 
28 #----------------------------------------
29 def treversal(root):
30     if root is not None:
31         print root.data,
32         treversal(root.left)
33         treversal(root.right)
34 
35 #----------------------------------------
36 # 
37 #----------------------------------------
38 def isIsomorphism(root1, root2):
39     if root1 is None and root2 is None:
40         return 1
41     if root1 and root2:
42         return isIsomorphism(root1.left, root2.left) \
43                 and  \
44                 isIsomorphism(root1.right, root2.right)
45     else:
46         return 0
47 
48 #----------------------------------------
49 # 
50 #----------------------------------------
51 def isSame(root1, root2):
52     if root1 is None and root2 is None:
53         return 1
54     if root1 and root2 and root1.data == root2.data:
55         return isSame(root1.left, root2.left) and \
56                 isSame(root1.right, root2.right)
57     else:
58         return 0
59 
60 treversal(n1)
61 
62 print ''
63 
64 if isIsomorphism(root1, root2.left):
65     print 'ISomorphism'
66 else:
67     print 'Not Isomorphism'
68 
69 if isSame(root1, root2.left):
70     print 'Same'
71 else:
72     print 'Not Same'