動機
複習dfs與bfs
Problem
Given the roots of two binary trees p
and q
, 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: p = [1,2,3], q = [1,2,3]Output: true
Example 2:
Input: p = [1,2], q = [1,null,2]Output: false
Example 3:
Input: p = [1,2,1], q = [1,1,2]Output: false
Constraints:
- The number of nodes in both trees is in the range
[0, 100]
. -104 <= Node.val <= 104
Sol
def bfs(root):
q = deque()
q.append(root)
ret = []
while q:
r = q.popleft()
if r:
q.append(r.left)
q.append(r.right)
ret.append(r.val)
else:
ret.append(None)
return ret
def dfs(r, ret):
if r:
ret.append(r.val)
return dfs(r.right,dfs(r.left,ret))
else:
ret.append(None)
return ret
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
return dfs(p,[]) == dfs(q,[])
Sol2
直接在tree上遞迴
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p is None and q is None:
return True
elif p is None or q is None:
return False
else:
return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)