forked from lilianweng/LeetcodePython
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsame_tree.py
More file actions
53 lines (45 loc) · 1.74 KB
/
same_tree.py
File metadata and controls
53 lines (45 loc) · 1.74 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#!/usr/bin/env python
'''
Leetcode: Same Tree
Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
'''
from __future__ import division
import random
from BinaryTree import Node
def is_same_tree(root1, root2):
if (not root1.left) and not (root1.right) and (not root2.left) and not (root2.right) and root1.value == root2.value:
return True
if (root1.value != root2.value) or (root1.left and not root2.left) or (not root1.left and root2.left) or (root1.right and not root2.right) or (not root1.right and root2.right): return False
left = is_same_tree(root1.left, root2.left) \
if root1.left and root2.left \
else True
right = is_same_tree(root1.right, root2.right) \
if root1.right and root2.right \
else True
return left and right
if __name__ == '__main__':
root1 = Node(value=5,
left=Node(value=4,
left=Node(value=11,
left=Node(value=6),
right=Node(value=2))
),
right=Node(value=8,
left=Node(value=13),
right=Node(value=4,
left=Node(value=5),
right=Node(value=1))
)
)
root2 = Node(value=0,
left=Node(value=4,
left=Node(value=11)
),
right=Node(value=8,
left=Node(value=13),
right=Node(value=4)
)
)
print is_same_tree(root1, root1)
print is_same_tree(root1, root2)