Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #100. Same Tree
- # 这道题有两种方法。第一种是用递归的方法,一个一个的比较,只要不相等就直接返回False。这种方法比较慢
- class Solution:
- def isSameTree(self, p, q):
- """
- :type p: TreeNode
- :type q: TreeNode
- :rtype: bool
- """
- if not p and not q:
- return True
- if not p or not q:
- return False
- if p and q and p.val == q.val:
- left = self.isSameTree(p.left, q.left)
- right = self.isSameTree(p.right, q.right)
- return left and right
- return False
- # 第二种方法是用 level order 的方法把 tree 转化成array然后进行比较
- from collections import deque
- class Solution2:
- def inorder(self, root, res):
- q = deque()
- q.append(root)
- while q:
- num = len(q)
- for i in range(0, num):
- node = q.popleft()
- if node:
- res.append(node.val)
- if node.left:
- q.append(node.left)
- else:
- q.append(None)
- if node.right:
- q.append(node.right)
- else:
- q.append(None)
- else:
- res.append(node)
- def isSameTree(self, p, q):
- """
- :type p: TreeNode
- :type q: TreeNode
- :rtype: bool
- """
- res1 = []
- res2 = []
- self.inorder(p, res1)
- self.inorder(q, res2)
- if len(res1) != len(res2):
- return False
- else:
- for i in range(0, len(res1)):
- if res1[i] != res2[i]:
- return False
- return True
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement