Question

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
/ \       / \
2   3     2   3

[1,2,3],   [1,2,3]

Output: true


Example 2:

Input:     1         1
/           \
2             2

[1,2],     [1,null,2]

Output: false


Example 3:

Input:     1         1
/ \       / \
2   1     1   2

[1,2,1],   [1,1,2]

Output: false


Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if p is None and q is None:
return True
elif p is not None and q is not None:
l = [(p, q)]
while True:
try:
(pnode, qnode) = l[-1]
del l[-1]
if pnode.val != qnode.val:
return False
if self.isSameStructure(pnode, qnode):
if pnode.left is not None:
l.append((pnode.left, qnode.left))
if pnode.right is not None:
l.append((pnode.right, qnode.right))
else:
return False
except IndexError:
return True
else:
return False

def isSameStructure(self, p, q):
if bool(p.left) != bool(q.left) or bool(p.right) != bool(q.right):
return False
else:
return True