FilesExpand file tree

 master

/

same-tree.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

32 lines (27 loc) · 1012 Bytes

 master

/

same-tree.py

Copy path

Top

File metadata and controls

• Code
• Blame

32 lines (27 loc) · 1012 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

# Time: O(n)

# Space: O(h), h is height of binary 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.

#

# Definition for a binary tree node

class TreeNode:

def __init__(self, x):

self.val = x

self.left = None

self.right = None

class Solution:

# @param p, a tree node

# @param q, a tree node

# @return a boolean

def isSameTree(self, p, q):

if p is None and q is None:

return True

if p is not None and q is not None:

return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

return False

if __name__ == "__main__":

root1, root1.left, root1.right = TreeNode(1), TreeNode(2), TreeNode(3)

root2, root2.left, root2.right = TreeNode(1), TreeNode(2), TreeNode(3)

print Solution().isSameTree(root1, root2)