100. same tree
100. Same Tree
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
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def isSameTree(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if (not p and q) or (p and not q):
return False
elif not p and not q:
return True
p_queue = deque([(1, p), ])
q_queue = deque([(1, q), ])
while p_queue and q_queue:
p_depth, p_root = p_queue.popleft()
q_depth, q_root = q_queue.popleft()
if p_depth != q_depth or p_root.val != q_root.val:
return False
if p_root.left and q_root.left:
if p_root.left.val == q_root.left.val:
p_queue.append((p_depth + 1, p_root.left))
q_queue.append((q_depth + 1, q_root.left))
else:
return False
elif not p_root.left and not q_root.left:
pass
else:
return False
if p_root.right and q_root.right:
if p_root.right.val == q_root.right.val:
p_queue.append((p_depth + 1, p_root.right))
q_queue.append((q_depth + 1, q_root.right))
else:
return False
elif not p_root.right and not q_root.right:
pass
else:
return False
print("return..")
return True
def isSameTree_32ms(self, p, q):
stack = [(p, q)]
while stack:
n1, n2 = stack.pop()
if n1 and n2 and n1.val == n2.val:
stack.append((n1.right, n2.right))
stack.append((n1.left, n2.left))
elif not n1 and not n2:
continue
else:
return False
return True
def isSameTree_recursion36ms(self, p, q):
"""
:type p: TreeNode
:type q: TreeNode
:rtype: bool
"""
if (not p and q) or (not q and p): return False
if not (p and q): return True
if p.val == q.val:
return self.isSameTree_recursion36ms(p.left, q.left) and \
self.isSameTree_recursion36ms(p.right, q.right)
else:
return False
